首页 > 代码库 > ZOJ2532_Internship
ZOJ2532_Internship
一个单源多汇的有向图,求增大那些边的容量可以使得网络的最大流增加。
很简单,直接跑最大流,保留残余网络,然后枚举所有余量为0的边,使其容量增加一个1,看看是否出现新的增广路即可。
召唤代码君:
#include <iostream>#include <cstring>#include <cstdio>#include <vector>#define maxn 555#define maxm 55555using namespace std;int to[maxm],c[maxm],next[maxm],first[maxn],edge;int d[maxn],tag[maxn],TAG=222;bool can[maxn];int Q[maxm],bot,top;int n,m,l,s,t;void _init(){ edge=-1; for (int i=0; i<=n+m+1; i++) first[i]=-1;}void addedge(int U,int V,int W){ edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){ Q[bot=top=1]=t,tag[t]=++TAG,d[t]=0,can[t]=false; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1] && tag[to[i]]!=TAG) { tag[to[i]]=TAG,d[to[i]]=d[cur]+1; can[to[i]]=false,Q[++top]=to[i]; if (to[i]==s) return true; } } return false;}int dfs(int cur,int num){ if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i] && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && !can[to[i]]) { k=dfs(to[i],min(c[i],num)); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (!num) break; } if (num) can[cur]=true; return tmp-num;}int main(){ int U,V,W,Flow=0; vector<int> ans; while (scanf("%d%d%d",&n,&m,&l) && (n|m|l)) { _init(); for (int i=1; i<=l; i++) { scanf("%d%d%d",&U,&V,&W); addedge(V,U,W); } s=0,t=n+m+1; for (int i=1; i<=n; i++) addedge(i,t,~0U>>1); while (bfs()) Flow+=dfs(s,~0U>>1); ans.clear(); for (int i=1; i<=l; i++) { if (c[i+i-2]) continue; c[i+i-2]++; if (bfs()) ans.push_back(i); c[i+i-2]--; } if (ans.size()>0) { printf("%d",ans[0]); for (unsigned i=1; i<ans.size(); i++) printf(" %d",ans[i]); } printf("\n"); } return 0;}
ZOJ2532_Internship
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。