Submit: 3016 Solved: 1279
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
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。
二分图匹配。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstdio> using namespace std; const int N=55; int n,tot,cnt,ans,head[N],match[N],p[N],g[N],f[N][N],Next[N*N],tree[N*N]; bool visit[N]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } bool find(int u) { for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (!visit[v]) { visit[v]=true; if (match[v]==0||find(match[v])) { match[v]=u; return true; } } } return false; } int main() { int T; scanf("%d",&T); while (T--) { scanf("%d",&n); tot=cnt=ans=0; for (int i=1;i<=n;i++) head[i]=0,match[i]=0; for (int i=1;i<=n;i++) scanf("%d",&p[i]); for (int i=1;i<=n;i++) { scanf("%d",&g[i]); if (p[i]==1&&g[i]==0) add(i,i); if (p[i]==0||(p[i]==1&&g[i]==0)) cnt++; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { scanf("%d",&f[i][j]); if (f[i][j]==1&&(p[i]==0||(p[i]==1&&g[i]==0))&&p[j]==1) add(i,j); } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) visit[j]=false; if (find(i)) ans++; } if (ans==cnt) puts("^_^");else puts("T_T"); } return 0; } |
