首页 > 代码库 > BZOJ2240 : ural1676 Mortal Combat
BZOJ2240 : ural1676 Mortal Combat
首先如果最大匹配不足$n$个那么显然每条边都不可能在匹配为$n$的方案中。
对于一条边$(u,v)$，如果它可能在最大匹配中，有两种情况：
$1.(u,v)$是当前方案的匹配边。
$2.$可以沿着$(u,v)$进行增广，那么在残余网络中$u$在$v$在一个环中，即属于同一个强连通分量。
因为源点不存在出边，因此只需加入汇点再求SCC即可。
时间复杂度$O(n^3)$。
#include<cstdio>const int N=1505,M=N*N;int n,m,T,i,j,b[N],f[N],g[N<<1],v[M],nxt[M],G[N<<1],V[M],NXT[M],ed,vis[N<<1],q[N<<1],t,id[N<<1];char a[N][N];bool find(int x){ for(int i=1;i<=m;i++)if(!b[i]&&a[x][i]){ b[i]=1; if(!f[i]||find(f[i]))return f[i]=x,1; } return 0;}inline void add(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed; V[ed]=x;NXT[ed]=G[y];G[y]=ed;}void dfs1(int x){ vis[x]=1; for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])dfs1(v[i]); q[++t]=x;}void dfs2(int x,int y){ vis[x]=0;id[x]=y; for(int i=G[x];i;i=NXT[i])if(vis[V[i]])dfs2(V[i],y);}int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++)for(scanf("%s",a[i]+1),j=1;j<=m;j++)a[i][j]-=‘0‘; for(i=1;i<=n;i++){ for(j=1;j<=m;j++)b[j]=0; if(!find(i)){ for(i=1;i<=n;puts(""),i++)for(j=1;j<=m;j++)putchar(‘1‘); return 0; } } T=n+m+1; for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j])if(f[j]==i)add(j+n,i);else add(i,j+n); for(i=1;i<=m;i++)if(f[i])add(T,i+n);else add(i+n,T); for(i=1;i<=T;i++)if(!vis[i])dfs1(i); for(i=t;i;i--)if(vis[q[i]])dfs2(q[i],q[i]); for(i=1;i<=n;puts(""),i++)for(j=1;j<=m;j++)if(a[i][j]&&(f[j]==i||id[i]==id[j+n]))putchar(‘0‘);else putchar(‘1‘); return 0;}
BZOJ2240 : ural1676 Mortal Combat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。