题目大意
给一个$n\times n$的矩阵，有$01$两种颜色，通过交换两行/列的颜色进行变换，询问是否存在一种方案使得矩阵主对角线均为$1$。
题目分析
我们建立二分图，左边的点表示行，右边的点表示主对角线上$1$的位置（纵坐标）。
对于一个$1$，就将其横纵坐标连边。
题目要求的是将这些行任意交换使得其与主对角线上的$1$的位置一一匹配，这就是二分图匹配的过程。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int t,n,vst[205],My[205];
bool map[205][205];
bool Dfs(int Now) {
for(int i=1; i<=n; i++) {
if(vst[i]||!map[Now][i])continue;
vst[i]=1;
if(My[i]==0||Dfs(My[i])) {
My[i]=Now;
return true;
}
}
return false;
}
int Hungary() {
memset(My,0,sizeof(My));
int ans=0;
for(int i=1; i<=n; i++) {
memset(vst,0,sizeof(vst));
if(Dfs(i))ans++;
}
return ans;
}
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
map[i][j]=Get_Int();
if(Hungary()==n)puts("Yes");
else puts("No");
}
return 0;
}
|
