洛谷 P1129 [ZJOI2007]矩阵游戏

题目传送门

解题思路：

将1所在的位置的行编号和列编号连边，跑二分图，如果最后能跑出二分图，说明有方案可以一行对应一列，一定可以通过一定变换找到目标状态。

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int t,n,head[201],tot,g[201];
 8 bool vis[201],p;
 9 struct kkk{
10     int to,next;
11 }e[200001][21];
12 
13 inline void chushihua() {
14     memset(head,0,sizeof(head));
15     tot = 0;
16     memset(g,0,sizeof(g));
17     p = 0;
18 }
19 
20 inline void add(int x,int y) {
21     e[++tot][t].to = y;
22     e[tot][t].next = head[x];
23     head[x] = tot;
24 }
25 
26 inline bool find(int x) {
27     for(int i = head[x];i; i = e[i][t].next) {
28         int u = e[i][t].to;
29         if(vis[u]) continue;
30         vis[u] = 1;
31         if(g[u] == 0 || find(g[u])) {
32             g[u] = x;
33             return true;
34         }
35     }
36     return false;
37 }
38 
39 int main() {
40     scanf("%d",&t);
41     while(t--) {
42         scanf("%d",&n);
43         chushihua();
44         for(int i = 1;i <= n; i++)
45             for(int j = 1;j <= n; j++) {
46                 int o;
47                 scanf("%d",&o);
48                 if(o == 1) 
49                     add(i,j);
50             }
51         for(int i = 1;i <= n; i++) {
52             memset(vis,0,sizeof(vis));
53             if(!find(i)) {
54                 p = 1;
55                 break;
56             }
57         }
58         if(!p) printf("Yes
");
59         else printf("No
");
60     }
61     return 0;
62 }