sgu 194 Reactor Cooling 无源无汇上下限网络流

前端之家收集整理的这篇文章主要介绍了sgu 194 Reactor Cooling 无源无汇上下限网络流前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<string.h>
  6. #include<queue>
  7. #define LL int
  8. #define inf 100000000
  9. #define maxn 1500
  10. using namespace std;
  11. struct pi
  12. {
  13. int to;
  14. int cost;
  15. int rev;
  16. int id;
  17. }pp;
  18. vector<pi >g[maxn];
  19. queue<int>q;
  20. int s,t;
  21. int line[maxn],leve[maxn];
  22. int min(int a,int b)
  23. {
  24. int p;
  25. p=a;
  26. if(b<a)
  27. p=b;
  28. return p;
  29. }
  30. void add(int a,int b,int cos,int id)
  31. {
  32. pp.to=b;
  33. pp.cost=cos;
  34. pp.id=id;
  35. pp.rev=(int)g[b].size();
  36. g[a].push_back(pp);
  37. pp.to=a;
  38. pp.cost=0;
  39. pp.id=-1;
  40. pp.rev=(int)g[a].size()-1;
  41. g[b].push_back(pp);
  42. return ;
  43. }
  44. void bfs(void)
  45. {
  46. q.push(s);
  47. int p,f,i;
  48. while(!q.empty())
  49. {
  50. p=q.front();
  51. q.pop();
  52. f=(int)g[p].size();
  53. for(i=0;i<f;i++)
  54. {
  55. pi &e=g[p][i];
  56. if(e.cost>0&&line[e.to]<0)
  57. {
  58. line[e.to]=line[p]+1;
  59. q.push(e.to);
  60. }
  61. }
  62. }
  63. return ;
  64. }
  65. int dfs(int v,int f)
  66. {
  67. int p;
  68. if(v==t)
  69. return f;
  70. for(int &i=leve[v];i<g[v].size();i++)
  71. {
  72. pi &e=g[v][i];
  73. if(line[v]<line[e.to]&&e.cost>0)
  74. {
  75. p=dfs(e.to,min(f,e.cost));
  76. if(p>0)
  77. {
  78. e.cost-=p;
  79. g[e.to][e.rev].cost+=p;
  80. return p;
  81. }
  82. }
  83. }
  84. return 0;
  85. }
  86. LL dinic()
  87. {
  88. int f;
  89. LL flow=0;
  90. while(1)
  91. {
  92. memset(line,-1,sizeof(line));
  93. memset(leve,sizeof(leve));
  94. line[s]=0;
  95. bfs();
  96. if(line[t]<0)
  97. return flow;
  98. f=dfs(s,inf);
  99. if(f==0)
  100. continue;
  101. flow+=f;
  102. while((f=dfs(s,inf))>0)
  103. {
  104. flow+=f;
  105. }
  106. }
  107. }
  108. int a[20005];
  109. struct ppi{
  110. int x;
  111. int y;
  112. int co1;
  113. int co2;
  114. }pp1[100005];
  115. int main()
  116. {
  117. int i,j,n,m,p,k,q;
  118. s=0;
  119. while(scanf("%d%d",&n,&m)!=EOF){
  120. t=n+1;
  121. for(i=0;i<=n+1;i++) g[i].clear();
  122. for(i=0;i<m;i++){
  123. scanf("%d%d%d%d",&pp1[i].x,&pp1[i].y,&pp1[i].co1,&pp1[i].co2);
  124. add(pp1[i].x,pp1[i].y,pp1[i].co2-pp1[i].co1,i);
  125. a[pp1[i].x]+=pp1[i].co1;
  126. a[pp1[i].y]-=pp1[i].co1;
  127. }
  128. for(i=1;i<=n;i++){
  129. if(a[i]>0) add(i,t,a[i],0);
  130. else add(s,i,-a[i],0);
  131. }
  132. p=dinic();
  133. memset(a,sizeof(a));
  134. k=0;
  135. f=g[0].size();
  136. for(i=0;i<f;i++){
  137. if(g[0][i].cost!=0){
  138. k=1;
  139. break;
  140. }
  141. }
  142. if(k) printf("NO\n");
  143. else{
  144. for(i=1;i<=n;i++){
  145. k=g[i].size();
  146. for(j=0;j<k;j++){
  147. if(g[i][j].id!=-1&&g[i][j].to!=s&&g[i][j].to!=t){
  148. a[g[i][j].id]=pp1[g[i][j].id].co2-g[i][j].cost;
  149. }
  150. }
  151. }
  152. printf("YES\n");
  153. for(i=0;i<m;i++){
  154. printf("%d\n",a[i]);
  155. }
  156. }
  157. }
  158. }

猜你在找的React相关文章