[bzoj1433]假期的宿舍

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 105
 4 struct ji{
 5     int nex,to;
 6 }edge[N*N];
 7 int E,t,n,s,x,p1[N],p2[N],head[N],mat[N],vis[N];
 8 void add(int x,int y){
 9     edge[E].nex=head[x];
10     edge[E].to=y;
11     head[x]=E++;
12 }
13 bool dfs(int k){
14     if (vis[k])return 0;
15     vis[k]=1;
16     for(int i=head[k];i!=-1;i=edge[i].nex)
17         if ((!mat[edge[i].to])||(dfs(mat[edge[i].to]))){
18             mat[edge[i].to]=k;
19             mat[k]=edge[i].to;
20             return 1;
21         }
22     return 0;
23 }
24 int main(){
25     scanf("%d",&t);
26     while (t--){
27         scanf("%d",&n);
28         for(int i=1;i<=n;i++)scanf("%d",&p1[i]);
29         for(int i=1;i<=n;i++)scanf("%d",&p2[i]);
30         memset(mat,0,sizeof(mat));
31         memset(head,-1,sizeof(head));
32         E=s=0;
33         for(int i=1;i<=n;i++)
34             if ((!p1[i])||(!p2[i])){
35                 s++;
36                 for(int j=1;j<=n;j++){
37                     scanf("%d",&x);
38                     if (i==j)x=1;
39                     if ((x)&&(p1[j]))add(i,j+n);
40                 }
41             }
42             else
43                 for(int j=1;j<=n;j++)scanf("%*d");
44         for(int i=1;i<=n;i++){
45             memset(vis,0,sizeof(vis));
46             s-=dfs(i);
47         }
48         if (!s)printf("^_^\n");
49         else printf("T_T\n");
50     }
51 }