[关闭]
@zzzc18 2017-05-13T00:25:35.000000Z 字数 2056 阅读 517

上下界网络流

网络流

有三种上下界网络流(最大流)
无源汇可行流/有源汇最大流/有源汇最小流

无源汇可行流

图片出自zsq--CSDN

原图

原图

把下界抽出来

把下界抽出来

连接到超级原点x,超级汇点y;想像一条不限上界的(y, x),用必要弧将它们“串”起来,即对于有向必要弧(u, v),添加(u, y),(x, v),容量为必要弧容量。这样就建立了一个等价的网络。 

连接到超级原点x,超级汇点y

一个无源汇网络的可行流的方案一定是必要弧是满的。若去掉(y, x)后,附加源x到附加汇y的最大流,能使得x的出弧或者y的入弧都满,充要于原图有可行流。 

去INF

  1. 按上述方法构造新网络(分离必要弧,附加源汇)
  2. 求附加源x到附加汇y的最大流
  3. 若x的出弧或y的入弧都满,则有解,将必要弧合并回原图;否则,无解
  1. #include<cstdio>
  2. #include<queue>
  3. #include<algorithm>
  4. #include<cstring>
  5. #define MAXN 205
  6. #define MAXE 30000
  7. #define INF 0x7fffffff
  8. using namespace std;
  9. int start,end;
  10. struct E{
  11. int next,to,val,id;
  12. }edge[MAXE];
  13. int edge_num=1,head[MAXN];
  14. int n,m,flow;
  15. int Node_flow[MAXN],ans[MAXE];
  16. int depth[MAXN],iter[MAXN],down[MAXE];
  17. queue<int> que;
  18. int EE;
  19. void addedge(int x,int y,int v,int z){
  20. edge[++edge_num].next=head[x];
  21. edge[edge_num].to=y;
  22. edge[edge_num].id=z;
  23. edge[edge_num].val=v;
  24. head[x]=edge_num;
  25. }
  26. void BFS(){
  27. memset(depth,-1,sizeof(depth));
  28. depth[n+1]=1;
  29. que.push(n+1);
  30. while(!que.empty()){
  31. int fro=que.front();que.pop();
  32. int i;
  33. for(i=head[fro];i;i=edge[i].next){
  34. if(edge[i].val>0 && depth[edge[i].to]==-1){
  35. depth[edge[i].to]=depth[fro]+1;
  36. que.push(edge[i].to);
  37. }
  38. }
  39. }
  40. }
  41. int DFS(int x,int flow){
  42. if(x==end)
  43. return flow;
  44. for(int &i=iter[x];i;i=edge[i].next){
  45. if(depth[edge[i].to]==depth[x]+1 && edge[i].val>0){
  46. int tmp=DFS(edge[i].to,min(edge[i].val,flow));
  47. if(tmp>0){
  48. edge[i].val-=tmp;
  49. edge[i^1].val+=tmp;
  50. return tmp;
  51. }
  52. }
  53. }
  54. return 0;
  55. }
  56. void Dinic(){
  57. while(true){
  58. BFS();
  59. if(depth[end]==-1)break;
  60. for(int i=1;i<=n+2;i++)
  61. iter[i]=head[i];
  62. while(DFS(start,INF));
  63. }
  64. }
  65. void solve(){
  66. Dinic();
  67. bool pd=true;
  68. int i;
  69. for(i=head[start];i;i=edge[i].next){
  70. if (edge[i].val>0){
  71. pd=false;break;
  72. }
  73. }
  74. if(!pd){printf("NO\n");return;}
  75. printf("YES\n");
  76. for(i=1;i<=EE;i++)
  77. ans[edge[i].id]=edge[i^1].val;
  78. for(i=1;i<=m;i++)
  79. printf("%d\n",ans[i]+down[i]);
  80. }
  81. int main(){
  82. freopen("in.in","r",stdin);
  83. freopen("out.out","w",stdout);
  84. scanf("%d%d",&n,&m);
  85. start=n+1;end=n+2;
  86. int i;
  87. for(i=1;i<=m;i++){
  88. int x,y,a,b;
  89. scanf("%d%d%d%d",&x,&y,&a,&b);
  90. addedge(x,y,b-a,i);
  91. addedge(y,x,0,0);
  92. Node_flow[y]+=a;
  93. Node_flow[x]-=a;
  94. down[i]=a;
  95. }
  96. EE=edge_num;
  97. for(i=1;i<=n;i++){
  98. if(Node_flow[i]>0){
  99. addedge(start,i,Node_flow[i],0);addedge(i,start,0,0);
  100. }
  101. if(Node_flow[i]<0){
  102. addedge(end,i,0,0);addedge(i,end,-Node_flow[i],0);
  103. }
  104. }
  105. solve();
  106. return 0;
  107. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注