二分图匹配。
如果i行j列是1，则i向j连边。如果这个二分图能够完全匹配了，则有解，反之无解。
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 7 #define N 222 8 #define M 55555 9 10 using namespace std; 11 12 int head[N],next[M],to[M]; 13 int cnt,n,linky[N]; 14 bool vis[N]; 15 16 inline void add(int u,int v) 17 { 18 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 19 } 20 21 inline void read() 22 { 23 memset(head,-1,sizeof head); cnt=0; 24 scanf("%d",&n); 25 for(int i=1,a;i<=n;i++) 26 for(int j=1;j<=n;j++) 27 { 28 scanf("%d",&a); 29 if(a) add(i,j); 30 } 31 } 32 33 inline bool dfs(int x) 34 { 35 for(int i=head[x];~i;i=next[i]) 36 { 37 if(vis[to[i]]) continue; 38 vis[to[i]]=true; 39 if(linky[to[i]]==-1||dfs(linky[to[i]])) 40 { 41 linky[to[i]]=x; 42 return true; 43 } 44 } 45 return false; 46 } 47 48 inline void go() 49 { 50 memset(linky,-1,sizeof linky); 51 for(int i=1;i<=n;i++) 52 { 53 memset(vis,0,sizeof vis); 54 dfs(i); 55 } 56 for(int i=1;i<=n;i++) 57 if(linky[i]==-1) {puts("No");return;} 58 puts("Yes"); 59 } 60 61 int main() 62 { 63 int cas; scanf("%d",&cas); 64 while(cas--) read(),go(); 65 return 0; 66 }