传送门

Description

[luogu1129 ZJOI2007] 矩阵游戏 (二分图最大匹配)-LMLPHP

Input

[luogu1129 ZJOI2007] 矩阵游戏 (二分图最大匹配)-LMLPHP

Output

[luogu1129 ZJOI2007] 矩阵游戏 (二分图最大匹配)-LMLPHP

Sample Input

2

2

0 0

0 1

3

0 0 1

0 1 0

1 0 0

Sample Output

No

Yes

HINT

[luogu1129 ZJOI2007] 矩阵游戏 (二分图最大匹配)-LMLPHP

Solution

经简单证明可知原题等价于给你一些黑色格子,问能否选出n个,使得每行、每列有且仅有一个黑色格子

那么直接对黑色格子的行列连边跑最小点覆盖

Code

//By Menteur_Hxy
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define E(i,u) for(register int i=head[u];i;i=nxt[i])
#define ins(a,b,c) add(a,b,c),add(b,a,0)
#define add(a,b,c) nxt[++cnt]=head[a],to[cnt]=b,cst[cnt]=c,head[a]=cnt
using namespace std; int read() {
int x=0,f=1; char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
return x*f;
} const int N=2010,INF=0x3f3f3f3f;
int n,S,T,cnt;
int nxt[N*N],to[N*N],cst[N*N],head[N<<1],cur[N<<1];
int que[N<<1],dis[N<<1]; bool bfs() {
memset(dis,0,sizeof(dis));
int h=0,t=1; que[++h]=S; dis[S]=1;
while(h<=t) {
int u=que[h++];
// cout<<u<<" "<<dis[u]<<endl;
E(i,u) if(!dis[to[i]]&&cst[i]>0)
dis[to[i]]=dis[u]+1,que[++t]=to[i];
}
return dis[T];
} int dfs(int u,int flow) {
if(u==T) return flow;
int used=0;
for(register int &i=cur[u],v;i;i=nxt[i]) {
// cout<<u<<" "<<to[i]<<" "<<cst[i]<<" "<<dis[to[i]]<<" "<<dis[u]<<endl;
if(cst[i]>0&&dis[(v=to[i])]==dis[u]+1) {
int tmp=dfs(v,min(flow-used,cst[i]));
cst[i]-=tmp,cst[i^1]+=tmp;
used+=tmp; if(used==flow) return flow;
}
} if(!used) dis[u]=-1;
return used;
} int dinic() {
int res=0;
while(bfs()) {
F(i,0,T) cur[i]=head[i];
res+=dfs(S,INF);
}
return res;
} int main() {
int cas=read();
while(cas--) {
n=read(); S=0,T=(n<<1|1),cnt=1;
memset(head,0,sizeof(head));
F(i,1,n) ins(S,i,1); F(i,1,n) ins(i+n,T,1);
F(i,1,n) F(j,1,n) if(read()) ins(i,j+n,1);
int res=dinic();
if(res==n) puts("Yes");
else puts("No");
}
return 0;
}
05-29 00:23