「ZJOI2007」矩阵游戏

发表于 | 分类于 | | 浏览量： 次

啥？又是二分图？

传送门

洛谷P1129

BZOJ1059

题解

对于这一题，可以把矩阵的每一行建一个点，矩阵的每一列建一个点。对于一个黑色格子，在它所在的行和列之间建边，这样就建出了一个二分图。

对于一个交换行或者交换列的操作，就相当于在图中交换两个点的编号。

当主对角线上的格子全部为黑色时，对应到图中就相当于每一行所对应的点都与和他编号相同的列对应的点之间有连边。

不难发现，当且仅当图中存在完美匹配时，可以达到可以达到目标状态。

所以直接上匈牙利算法求二分图最大匹配即可。

代码

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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=205;
int T,n,tot,lnk[maxn],son[maxn*maxn],nxt[maxn*maxn],cp[maxn],ans;bool vis[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
bool Hungary(int now)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(!vis[son[i]])
		{
			vis[son[i]]=true;
			if(!cp[son[i]]||Hungary(cp[son[i]]))
			{
				cp[son[i]]=now;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();memset(lnk,0,sizeof(lnk));memset(cp,0,sizeof(cp));tot=ans=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(read())
					add_e(i,j);
		for(int i=1;i<=n;i++)
		{
			memset(vis,0,sizeof(vis));
			if(Hungary(i)) ans++;
		}
		printf("%s\n",ans==n?"Yes":"No");
	}
	return 0;
}