洛谷P1129 [ZJOI2007]矩阵游戏 题解

题目链接：https://www.luogu.org/problemnew/show/P1129

分析：

这道题不是很好想，但只要想的出来，代码不成问题。

思路1

举几个例子，我们发现，

对于任何数来说，同一行的永远在同一行，同一列的永远在同一列

进一步研究，发现所有行所有列要有1，且至少要有n个1两两不同行不同列

对于每个$1$，设坐标为$(x,y)$，那么$x$行向$y$列连边

判断是否有完全匹配（都能匹配上），能匹配上就可以

思路2

这个就是比较拓展的思路了，如果你学了高等数学的话，应该知道有个叫行列式的东西（百度一下？），我们只需判断行列式是否等于0（每一个矩阵中的数字都乘上除去这一行这一列的其他所有数），即可求得答案。

PS：由于作者对此了解有限，讲述不对之处欢迎_踢提出！

代码：

#include<cstdio>
#include<vector>
#include<cstring> 
using namespace std;
vector<int>e[205];
int link[205];
int vis[205];
int t;
int find(int x)
{
	for(int i=0;i<e[x].size();i++)
	{
		int p=e[x][i];
		if(vis[p]!=t)
		{
			vis[p]=t;
			if(!link[p]||find(link[p]))
			{
				link[p]=x;
				return 1;
			}
		}
	} 
	return 0;
}
int main()
{
	int T,n,tmp,cnt;
	scanf("%d",&T);
	while(T--)
	{
		cnt=0;
		t=0;
		
		memset(vis,0,sizeof(vis));
		memset(link,0,sizeof(link));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		e[i].clear();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&tmp);
				if(tmp==1)
				{
					e[i].push_back(j);
				}
			} 
		} 
		for(int i=1;i<=n;i++)
		{
			t++;
			if(find(i))
			{
				cnt++;
			}
			else
			break;
		}
		if(cnt==n)
		{
			printf("Yes\n");
		} 
		else
		printf("No\n");
	} 
	return 0;
}