即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[bzoj1433][ZJOI2009]假期的宿舍 二分图最大匹配

编程语言 youhavepeople 25℃ 0评论
本文目录
[隐藏]

1.1433: [ZJOI2009]假期的宿舍

Time Limit: 10 Sec  Memory Limit:
162 MB


[Submit][Status][Discuss]

2.Description

3.Input

4.Output

5.Sample Input

1


3


1 1 0


0 1 0


0 1 1


1 0 0


1 0 0

6.Sample Output

ˆ ˆ


7.HINT

对于30% 的数据满足1 ≤ n ≤ 12。


对于100% 的数据满足1 ≤ n ≤ 50,1 ≤ T ≤ 20。

8.Source

考这么水的题,愣是被我数组开小RE了8个点
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
const int N = 205;
int last[N],S,T,n,h[N],q[N],cnt=1,cur[N],sign[N],ans,MT,inclass[N];
struct Edge{
 int to,next,v;
}e[N*4];
void insert( int u, int v, int w ){
 e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt;
 e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt;
}
bool bfs(){
 memset(h,-1,sizeof(h));
 int tail = 1, head = 0;
 q[0] = 0; h[0] = 0;
 while( tail != head ){
  int now = q[head++];
  for( int i = last[now]; i; i = e[i].next )
   if( h[e[i].to] == -1 && e[i].v ){
    h[e[i].to] = h[now] + 1;
    q[tail++] = e[i].to;
   }
 }
 return h[T] != -1;
}
int dfs( int x, int f ){
 int w,used=0;
 if( x == T ) return f;
 for( int i = cur[x]; i; i = e[i].next )
  if( h[e[i].to] == h[x] + 1 ){
   w = dfs(e[i].to,min(e[i].v,f-used));
   e[i].v -= w; e[i^1].v += w; used += w;
   if( e[i].v ) cur[x] = i; if( f == used ) return f;
  }
 if( !used ) h[x] = -1;
 return used;
}
void dinic(){
 while( bfs() ){
  for( int i = S; i <= T; i++ ) cur[i] = last[i];
  ans += dfs(S,INF);
 }
}
int main(){
 scanf("%d", &MT);
 while( MT-- ){
  scanf("%d", &n); S = 0; T = n*2+1; int yu = n; ans = 0;
  cnt = 1; memset(last,0,sizeof(last)); memset(sign,0,sizeof(sign));
  for( int i = 1; i <= n; i++ ) scanf("%d", &inclass[i]);
  for( int i = 1,x; i <= n; i++ ){ scanf("%d", &x); if( inclass[i] && x == 1 ) sign[i] = 1; }
  for( int i = 1; i <= n; i++ ) if( !sign[i] ) insert(S,i,1);
  for( int i = 1; i <= n; i++ ) if( inclass[i] ) insert(i+n,T,1);
  for( int i = 1; i <= n; i++ )
   for( int j = 1,x; j <= n; j++ ){
    scanf("%d", &x);
    if( sign[i] || !inclass[j] ) continue;
    if( x || i == j ) insert(i,j+n,1);
   }
  for( int i = 1; i <= n; i++ ) if( sign[i] ) yu--;
  dinic();
  /*for( int i = S; i <= T; i++ ){
   for( int j = last[i]; j; j = e[j].next )
    printf("%d ", e[j].to);
   puts("");
  }
  printf("%d\n", ans);*/
  if( ans == yu ) puts("^_^");
  else puts("T_T");
 }
 return 0;
}


转载请注明:CodingBlog » [bzoj1433][ZJOI2009]假期的宿舍 二分图最大匹配

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情