首页 > 代码库 > 【POJ1815】Friendship 网络流最小割
【POJ1815】Friendship 网络流最小割
题意:若干个人,然后给出s、t和连边矩阵,问最少搞死多少个人可以让s和t这两个(不可以被搞死)的人不连通。(还要字典序最小的方案)
题解:最小割,首先我们拆点,两部分流量为1来满足性质,然后连inf的联通边。
然后跑一遍就出来需要几个人了。
如果是inf就NO answer
然后我们从小到大枚举哪个人在最小割集里面,即把此人删掉再跑,看maxflow。
然后AC。
注意题意中说如果是需要杀人,第二行就输出这些人。
但是没说不需要时怎么办。
经过检测,输不输出空行都行,由此推测,没有这种情况。
代码:
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 2000 // 网络图中点 #define G 1000000 // 网络图中边 #define inf 0x3f3f3f3f using namespace std; struct KSD { int v,next,len; }e[G]; int head[N],cnt; void add(int u,int v,int len) { cnt++; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } queue<int>q; int d[N],s,t; bool bfs() { memset(d,0,sizeof(d)); int i,u,v; while(!q.empty())q.pop(); q.push(s),d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next)if(e[i].len) { v=e[i].v; if(!d[v]) { d[v]=d[u]+1; if(v==t) return 1; q.push(v); } } } return 0; } int dinic(int x,int flow) { if(x==t)return flow; int remain=flow,k; int i,v; for(i=head[x];i&&remain;i=e[i].next) { v=e[i].v; if(e[i].len&&d[v]==d[x]+1) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i^1].len+=k,e[i].len-=k; remain-=k; } } return flow-remain; } int n,m,p,maxflow; int S,T,ans; int map[1005][1005]; bool vis[N]; void build() { int i,j; cnt=1; memset(head,0,sizeof(head)); for(i=1;i<=n;i++)if(!vis[i])add(i,i+n,1),add(i+n,i,0); for(i=1;i<=n;i++)if(!vis[i])for(j=1;j<=n;j++)if(!vis[j]) { if(i==j)continue; if(map[i][j])add(i+n,j,inf),add(j,i+n,0); } } bool work() { if(scanf("%d%d%d",&n,&S,&T)==EOF)return 0; int i,j,k,flag=0; s=S+n,t=T; for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&map[i][j]); build(); ans=0; while(bfs()) { k=dinic(s,inf); if(k==inf){puts("NO ANSWER!");return 1;} else ans+=k; } printf("%d\n",ans); if(ans)flag=1; for(i=1;i<=n;i++)if(i!=S&&i!=T) { vis[i]=1; build(); maxflow=0; while(bfs())maxflow+=dinic(s,inf); if(maxflow<ans)printf("%d ",i),ans=maxflow; else vis[i]=0; } puts(""); return 1; } int main() { freopen("test.in","r",stdin); while(work()); }
【POJ1815】Friendship 网络流最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。