[ZJOI2007]矩阵游戏

# 题意 允许交换01矩阵的任意两行或者两列，求能否使得某一条对角线上的数全部为1 $n\leq 200$，多组数据 <!--more--> # 分析 其实相当于放n个互补攻击的车，因为n个互不攻击的车可以通过交换行列形成一条对角线 因此把行和列二分图匹配即可 # 代码 ```cpp #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=1000,M=200000,INF=0x3f3f3f3f; int T,n,s,t; int a[N][N]; struct qxx{int nex,t,v;}; qxx e[M]; int h[N],cur[N],cnt=1; void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;} void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);} int rk[N]; bool bfs(){ queue<int> q; memset(rk,0,sizeof(rk)); memcpy(cur,h,sizeof(cur)); q.push(s),rk[s]=1; while(q.size()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v); } } return rk[t]; } int dinic(int u,int flow){ if(u==t)return flow; int x,rest=flow; for(int i=cur[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(!w||rk[v]!=rk[u]+1)continue; x=dinic(v,min(w,rest)); if(x)e[i].v-=x,e[i^1].v+=x,rest-=x; else rk[v]=0; if(!rest)cur[u]=i; } if(rest)cur[u]=0;//当前弧优化 return flow-rest; } int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); memset(h,0,sizeof(h)); cnt=1,s=0,t=n+n+1; for(int i=1;i<=n;i++){ add_flow(s,i,1);add_flow(i+n,t,1); for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); if(a[i][j])add_flow(i,j+n,1); } } int maxflow=0; while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i; puts(maxflow==n?"Yes":"No"); } return 0; } //r[i]:i //c[i]:i+n ```