acdream 1211 Reactor Cooling 网络流

前端之家收集整理的这篇文章主要介绍了acdream 1211 Reactor Cooling 网络流前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

传送门:acdream 1211

给定n个点,以及它们之间的m个管道,每个管道有流量的最小限制和最大限制,问能否存在一种情况,使得所有管道内的流量都满足流量限制


带上下界的网络流,如果不考虑流量的最小限制,那就是单纯的网络流问题,因此这里只需要转化一下即可。

对于每一条管道,将最小限制加到入口的出度,加到出口的入度,求出所有点的总入度与总出度,总入度大的,建立一个源点指向该点,流量即为该点入度与出度之差,总出度大的,该点建一条边指向一个汇点,流量为出度与入度之差,然后每条管道的流量限制都更新为最@R_224_403@与最小流量之差,对于建立的新图跑一遍网络流,如果是汇源满流则说明可行,每条管道的流量即为新图的当前流量与该管道的最小流量限制之和。

  1. /******************************************************
  2. * File Name: b.cpp
  3. * Author: kojimai
  4. * Creater Time:2014年10月01日 星期三 16时00分06秒
  5. ******************************************************/
  6.  
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<queue>
  10. #include<cmath>
  11. #include<algorithm>
  12. #include<iostream>
  13. using namespace std;
  14. #define FFF 205
  15. int first[FFF],in[FFF],e,dis[FFF];
  16. struct node
  17. {
  18. int v,f,l,next;
  19. }edge[50005];
  20. void addedge(int x,int y,int l,int c)
  21. {
  22. edge[e].v=y;edge[e].next=first[x];edge[e].l=l;edge[e].f=c;first[x]=e++;
  23. edge[e].v=x;edge[e].next=first[y];edge[e].l=0;edge[e].f=0;first[y]=e++;
  24. }
  25. bool bfs(int s,int t)
  26. {
  27. memset(dis,-1,sizeof(dis));
  28. dis[s] = 0;
  29. queue<int> q;
  30. q.push(s);
  31. while(!q.empty())
  32. {
  33. int now = q.front();q.pop();
  34. for(int k = first[now];k!=-1;k = edge[k].next)
  35. {
  36. if(edge[k].f-edge[k].l>0 && dis[edge[k].v] ==-1)
  37. {
  38. dis[edge[k].v] = dis[now] + 1;
  39. if(edge[k].v == t)
  40. return true;
  41. q.push(edge[k].v);
  42. }
  43. }
  44. }
  45. return false;
  46. }
  47. int dfs(int now,int flow,int t)
  48. {
  49. int f;
  50. if(now == t)
  51. return flow;
  52. for(int k = first[now];k != -1;k = edge[k].next)
  53. {
  54. if(edge[k].f - edge[k].l > 0 && dis[edge[k].v] == dis[now] + 1 && (f=dfs(edge[k].v,min(flow,edge[k].f - edge[k].l),t)))
  55. {
  56. edge[k].f -= f;
  57. edge[k^1].f += f;
  58. return f;
  59. }
  60. }
  61. return 0;
  62. }
  63. int dinic(int s,int t)
  64. {
  65. int flow,ret = 0;
  66. while(bfs(s,t))
  67. {
  68. while(flow=dfs(s,233333333,t))
  69. ret += flow;
  70. }
  71. return ret;
  72. }
  73. int main()
  74. {
  75. int n,m,x,y,c;
  76. while(~scanf("%d%d",&n,&m))
  77. {
  78. memset(first,sizeof(first));
  79. memset(in,sizeof(in));
  80. e=0;
  81. for(int i=0;i<m;i++)
  82. {
  83. scanf("%d%d%d%d",&x,&y,&l,&c);
  84. addedge(x,c);
  85. in[x]-=l;in[y]+=l;
  86. }
  87. int sum = 0;
  88. for(int i=1;i<=n;i++)
  89. {
  90. if(in[i]>0)
  91. {
  92. addedge(0,i,in[i]);
  93. sum += in[i];
  94. }
  95. else if(in[i]<0)
  96. addedge(i,n+1,-in[i]);
  97. }
  98. int ans = dinic(0,n+1);
  99. if(sum == ans)
  100. {
  101. printf("YES\n");
  102. for(int i=0;i<m;i++)
  103. printf("%d\n",edge[i*2].l+edge[i*2+1].f);
  104. }
  105. else
  106. printf("NO\n");
  107. }
  108. return 0;
  109. }

猜你在找的React相关文章