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

Description

Input

Output

Sample Input

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

Sample Output

ˆ_ˆ

题解

好裸的二分图匹配。。闲得无聊居然翻到一道水题，zj666
那么就是外校的跟本校能提供床位的人连边，和本校的互相连啦，总之按题意来
注意如果i是学生且不回家的话要向自己连边！！！

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int match[60],back[60],s[60],n;
bool chw[60],map[60][60];
bool find_muniu(int x)
{
for(int j=1;j<=n;j++)
if(map[x][j]==true)
if(chw[j])
            {
                chw[j]=false;
if(match[j]==0 || find_muniu(match[j])){match[j]=x;return true;}
            }
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
    {
scanf("%d",&n);
memset(match,0,sizeof(match));
memset(map,false,sizeof(map));
for(int i=1;i<=n;i++)scanf("%d",&s[i]);
for(int i=1;i<=n;i++)scanf("%d",&back[i]);
for(int i=1;i<=n;i++)
        {
for(int j=1;j<=n;j++)
            {
int x;
scanf("%d",&x);
if(x==1)
                {
if(back[i]==1 && s[i]==1)map[j][i]=true;
if(s[i]==1 && s[j]==1)map[i][j]=map[j][i]=true;
if(s[i]==0 && s[j]==1)map[i][j]=true;
if(s[i]==1 && s[j]==0)map[j][i]=true;
                }
if(x==0 && s[i]==1 && back[i]==0)map[i][i]=true;//不回家。在学校要给自己连边。。 
            }
        }
int ans=0;
for(int i=1;i<=n;i++)
        {
memset(chw,true,sizeof(chw));
if(back[i]==1 && s[i]==1){ans++;continue;}
if(find_muniu(i))ans++;
        }
if(ans==n)printf("^_^\n");
else printf("T_T\n");
    }
return 0;
}