很容易想到去吧棋盘模型转为二分图。
发现是一个类似行列匹配的问题。 进一步，如果每一个行都可以找到一个列与之配对的话，一定可以通过交换满足要求。 直接dinic求二分图最大匹配即可。#include#include #include #include #include #include #include #include #include #define N 110000#define eps 1e-7#define inf 1e9+7#define ll long longusing namespace std;inline int read(){ char ch=0; int x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}struct edge{ int to,nxt,w;}e[N*2];int num,head[N];inline void add(int x,int y,int z){ e[++num]=(edge){y,head[x],z};head[x]=num; e[++num]=(edge){x,head[y],0};head[y]=num;}queue q;int n,m,s,t,dep[N];bool bfs(){ for(int i=0;i<=t;i++)dep[i]=0; dep[s]=1;q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x];i!=-1;i=e[i].nxt) { int to=e[i].to; if(!dep[to]&&e[i].w) { dep[to]=dep[x]+1; q.push(to); } } } return dep[t];}int dfs(int x,int flow){ if(x==t)return flow; for(int i=head[x];i!=-1;i=e[i].nxt) { int to=e[i].to; if(dep[to]==dep[x]+1&&e[i].w) { int w=dfs(to,min(flow,e[i].w)); if(w) { e[i].w-=w; e[i^1].w+=w; return w; } } } return 0;}void work(){ int n=read(),i,j,w,maxflow=0; num=-1;memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(read())add(i,j+n,1); s=2*n+1;t=2*n+2; for(i=1;i<=n;i++) { add(s,i,1); add(i+n,t,1); } while(bfs()) { do { w=dfs(s,inf); maxflow+=w; }while(w); } if(maxflow==n)printf("Yes\n"); else printf("No\n"); return;}int main(){ int t=read(); for(int i=1;i<=t;i++)work(); return 0;}