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

分析:

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

思路1

举几个例子,我们发现,

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

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

对于每个111,设坐标为(x,y)(x,y)(x,y),那么xxx行向yyy列连边

判断是否有完全匹配(都能匹配上),能匹配上就可以

思路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;
}