sgu194:Reactor Colling(无源无汇上下界最大流)

前端之家收集整理的这篇文章主要介绍了sgu194:Reactor Colling(无源无汇上下界最大流)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
题意:
求一个无源无汇的有上下界的最大流。
分析:

把每条边的边容量重设为上界-下界,记录每个点的最小进入in和最小输出流out,重设一个s、t,将s、t连向每一个点,边容量分别为每个点的in和out,从s到t跑最大流即

可。如果s的每条边满流,则有解,否则无解。

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. using namespace std;
  5. const int MAXN = 209,INF = 1e9;
  6. int n,m;
  7. struct Edge
  8. {
  9. int v,ne;
  10. int f,c,l;
  11. }edge[MAXN*MAXN];
  12. int edgehead[MAXN],p = 1;
  13. int sum,in[MAXN],out[MAXN];
  14. int dis[MAXN];
  15.  
  16. void add(int u,int v,int f,int l)
  17. {
  18. edge[p].v = v;edge[p].c = edge[p].f = f;edge[p].l = l;
  19. edge[p].ne = edgehead[u];edgehead[u] = p++;
  20. }
  21.  
  22. int adv(int k) {return ((k-1)^1)+1;}
  23.  
  24. bool bfs(int s,int t)
  25. {
  26. for(int i = 1; i <= n; ++i) dis[i] = INF;
  27. dis[t] = 0;
  28. queue<int> q;
  29. q.push(t);
  30. while(!q.empty())
  31. {
  32. int u = q.front();q.pop();
  33. for(int i = edgehead[u]; i; i = edge[i].ne)
  34. {
  35. int v = edge[i].v,f = edge[adv(i)].f;
  36. if(f && dis[v] > dis[u]+1)
  37. {
  38. dis[v] = dis[u]+1;
  39. q.push(v);
  40. }
  41. }
  42. }
  43. return dis[s] != INF;
  44. }
  45.  
  46. int dfs(int now,int t,int flow)
  47. {
  48. if(now == t || flow == 0) return flow;
  49. int re = 0,tmp;
  50. for(int i = edgehead[now]; i; i = edge[i].ne)
  51. {
  52. int to = edge[i].v;
  53. if(dis[to] == dis[now]-1 && edge[i].f && (tmp = dfs(to,t,min(flow,edge[i].f))))
  54. {
  55. re += tmp;flow -= tmp;
  56. edge[i].f -= tmp;edge[adv(i)].f += tmp;
  57. if(flow == 0) break;
  58. }
  59. }
  60. dis[now] = INF;
  61. return re;
  62. }
  63.  
  64. int dinic(int s,int maxf)
  65. {
  66. int re = 0;
  67. while(bfs(s,t))
  68. re += dfs(s,maxf);
  69. return re;
  70. }
  71.  
  72. int main()
  73. {
  74. scanf("%d%d",&n,&m);
  75. for(int i = 1; i <= m; ++i)
  76. {
  77. int a,b,d;
  78. scanf("%d%d%d%d",&a,&b,&c,&d);
  79. in[b] += c;out[a] += c;sum += c;
  80. add(a,d-c,c);
  81. add(b,a,0);
  82. }
  83. for(int i = 1; i <= n; ++i)
  84. {
  85. if(in[i]) add(n+1,i,in[i],0),add(i,n+1,0);
  86. if(out[i]) add(i,n+2,out[i],add(n+2,0);
  87. }
  88. n += 2;
  89. if(dinic(n-1,n,INF) != sum)
  90. {
  91. puts("NO");
  92. goto end;
  93. }
  94. puts("YES");
  95. for(int i = 1; i <= m; ++i)
  96. printf("%d\n",edge[2*i-1].c-edge[2*i-1].f+edge[2*i-1].l);
  97. end:;
  98. return 0;
  99. }

猜你在找的React相关文章