我們發現同行同列的點無論經過多少次變換仍然同行或同列，所以題目可轉換為能不能找到n個互相不同行或同列的點，
那么我們用二分圖求一下最大匹配即可，
#include <bits/stdc++.h>
using namespace std;
const int N=205;
int T,n,x,ans;
int match[N<<1];
bool vis[N<<1];
int cnt,head[N<<1];
struct edge{int next,to;}e[N*N];
inline void add(int u,int v)
{
cnt++;
e[cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
int dfs(int u)
{
for (register int i=head[u]; i; i=e[i].next)
if (!vis[e[i].to])
{
vis[e[i].to]=true;
if (!match[e[i].to] || dfs(match[e[i].to]))
{
match[e[i].to]=u;
return 1;
}
}
return 0;
}
int main(){
scanf("%d",&T);
while (T--)
{
cnt=0; memset(head,0,sizeof(head));
scanf("%d",&n);
for (register int i=1; i<=n; ++i)
for (register int j=1; j<=n; ++j)
{
scanf("%d",&x);
if (x) add(i,j);
}
ans=0; memset(match,0,sizeof(match));
for (register int i=1; i<=n; ++i)
{
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
if (ans==n) puts("Yes"); else puts("No");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/44631.html
標籤：其他
上一篇：013:魔獸世界之一：備戰
下一篇：C#：類與物件_創建玩家類