[文章目录]
Description
给你一个n*n棋盘，每个格子上有黑或白子，游戏规则是交换任意行列，不限次数，使主对角线上全部为黑子。问是否有解。n<=200
一开始想判断是否有一行或有一列没有子，然后进行判断。但是忽略了即使行列都有黑子，当你选了一行对应一列时，该行列上的黑子都相当于没用了。
然后受行列式影响，就开始推矩阵的秩。然而答案并不是只有主对角线上有黑子。
最后发现是二分图最大匹配。将行和列匹配，是的每一行都有对应的列上的黑子就是Yes。
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int s,t,T,n,ans;
int head[500],to[101000],nxt[101000],data[101000],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
data[cnt]=0;
}
queue<int>q;
int dis[500];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
dis[s]=0;q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i])
if(data[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int tmp=flow,xx;
for(int i=head[x];i;i=nxt[i])
if(data[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,data[i]));
if(!xx) dis[to[i]]=-1;
data[i]-=xx;data[i^1]+=xx;tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(head,0,sizeof(head));cnt=1;
ans=0;
scanf("%d",&n);
int x;s=2*n+1,t=2*n+2;
for(int i=1;i<=n;i++)
{
add(s,i,1);add(i+n,t,1);
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
if(x) add(i,j+n,1);
}
}
while(bfs()) ans+=dinic(s,1<<30);
if(ans==n) puts("Yes");
else puts("No");
}
return 0;
}