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

Description

Input

Output

Sample Input

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

Sample Output

ˆ ˆ

HINT

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

最近被二分图到底要用邻接矩阵还是邻接表搞得十分分裂。。

还是看图的稠密程度吧？？？

这题的建图十分经典，对于每一个本校学生对自己的床连边，其他连边同输入的矩阵。

本质虽然是匈牙利算法求二分图最大匹配，事实上不用把最大匹配求出来，只要增广到对于一个需要住校的人没有床睡就好了。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int maxn=;

 int T,n,n_l,n_r;

 int E[maxn][maxn],stu[maxn],hom[maxn],mat[maxn];

 bool check[maxn];

 bool dfs(int x){

     for(int i=;i<=n_r;i++)

         if(stu[i]&&E[x][i]&&!check[i]){

             check[i]=;

             if(mat[i]==-||dfs(mat[i])){

                 mat[i]=x;

                 return ;

             }

         }

     return ;

 }

 bool hungary(){

     memset(mat,-,sizeof mat);

     for(int i=;i<=n;i++){

         memset(check,,sizeof check);

         if(!hom[i]&&!dfs(i))  return ;

     }

     return ;

 }

 void init(){

     scanf("%d",&n);  n_l=n_r=n;

     for(int i=;i<=n;i++)  scanf("%d",&stu[i]);

     for(int i=;i<=n;i++){

         scanf("%d",&hom[i]);

         if(!stu[i])  hom[i]=;

     }

     for(int i=;i<=n;i++){

         for(int j=;j<=n;j++)

             scanf("%d",&E[i][j]);

         if(stu[i])  E[i][i]=;

     }

 }

 int main(){

     scanf("%d",&T);

     while(T--){

         init();

         puts(hungary()?"^_^":"T_T");

     }

     return ;

 }

巴特西