「ZJOI2007」矩阵游戏 - 二分图匹配 | Bill Yang's Blog

「ZJOI2007」矩阵游戏 - 二分图匹配

题目大意

给一个$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;
}
本篇文章有用吗?有用还不快点击!
0%