zoj 2314 Reactor Cooling 有上下界的网络最大流

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

输出的时候发现不会对原来的矩阵排序,只好重新搞了一储存边的一维数组,然后排序。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=256;
  4. const int inf=0x7fffffff;
  5.  
  6. struct type
  7. {
  8. int b,c,f;
  9. int no;
  10. };
  11. struct node
  12. {
  13. int no,f;
  14. }g[20000+5];
  15. int cmp(node a,node b)
  16. {
  17. return a.no<b.no;
  18. }
  19.  
  20. type Edge[N][N];
  21. type AccEdge[N][N];
  22. int n,m;
  23. int flag[N],p[N],a[N];
  24.  
  25. void Ford(type network[][N],int s,int t)
  26. {
  27. int i,j,u;
  28. while(1)
  29. {
  30. memset(flag,0xff,sizeof(flag));
  31. memset(p,sizeof(p));
  32. memset(a,sizeof(a));
  33. flag[s]=0;
  34. p[s]=0;
  35. a[s]=inf;
  36. queue<int>Q;
  37. Q.push(s);
  38. while(!Q.empty()&&flag[t]==-1)
  39. {
  40. u=Q.front();
  41. Q.pop();
  42. for(i=s; i<=t; i++)
  43. {
  44. if(flag[i]!=-1) continue;
  45. if(network[u][i].c<inf&&network[u][i].f<network[u][i].c)
  46. {
  47. flag[i]=0;
  48. p[i]=u;
  49. a[i]=min(a[u],network[u][i].c-network[u][i].f);
  50. Q.push(i);
  51. }
  52. else if(network[i][u].c<inf&&network[i][u].f>network[i][u].b)
  53. {
  54. flag[i]=0;
  55. p[i]=u;
  56. a[i]=min(a[u],network[i][u].f-network[i][u].b);
  57. Q.push(i);
  58. }
  59. }
  60. flag[u]=1;
  61. }
  62. if(flag[t]==-1||a[t]==0) break;
  63. int k1=t,k2=p[k1];
  64. while(1)
  65. {
  66. if(network[k2][k1].f<inf)
  67. network[k2][k1].f=network[k2][k1].f+a[t];
  68. else
  69. network[k1][k2].f=network[k1][k2].f-a[t];
  70. if(k2==s) break;
  71. k1=k2;
  72. k2=p[k1];
  73. }
  74. }
  75. }
  76.  
  77. void accompany()
  78. {
  79. memcpy(AccEdge,Edge,sizeof(Edge));
  80. int i,sum1,sum2;
  81. for(i=1; i<=n; i++)
  82. {
  83. sum1=sum2=0;
  84. for(j=1; j<=n; j++)
  85. {
  86. if(AccEdge[i][j].b!=inf) sum1+=AccEdge[i][j].b;
  87. if(AccEdge[j][i].b!=inf) sum2+=AccEdge[j][i].b;
  88. }
  89. if(sum2>sum1)
  90. AccEdge[0][i].c=sum2-sum1,AccEdge[0][i].b=AccEdge[0][i].f=0;
  91. else
  92. AccEdge[i][n+1].c=sum1-sum2,AccEdge[i][n+1].b=AccEdge[i][n+1].f=0;
  93. }
  94. for(i=1; i<=n; i++)
  95. for(j=1; j<=n; j++)
  96. if(AccEdge[i][j].c!=inf)
  97. {
  98. AccEdge[i][j].c=AccEdge[i][j].c-AccEdge[i][j].b;
  99. AccEdge[i][j].b=0;
  100. }
  101. Ford(AccEdge,0,n+1);
  102. bool ok=1;
  103. for(i=0; i<=n+1; i++)
  104. {
  105. if(AccEdge[0][i].c!=inf&&AccEdge[0][i].f!=AccEdge[0][i].c)
  106. ok=0;
  107. }
  108. if(!ok) printf("NO\n");
  109. else
  110. {
  111. int tp=0;
  112. printf("YES\n");
  113. for(i=1; i<=n; i++)
  114. for(j=1; j<=n; j++)
  115. if(Edge[i][j].c!=inf)
  116. {
  117. Edge[i][j].f=AccEdge[i][j].f+Edge[i][j].b;
  118. g[tp].f=Edge[i][j].f;
  119. g[tp].no=Edge[i][j].no;
  120. tp++;
  121. }
  122. sort(g,g+tp,cmp);
  123. for(i=0;i<tp;i++)
  124. printf("%d\n",g[i].f);
  125. }
  126. }
  127. int main()
  128. {
  129. int _,i,u,v,b,c;
  130. scanf("%d",&_);
  131. while(_--)
  132. {
  133. scanf("%d%d",&n,&m);
  134. for(i=0; i<n+2; i++)
  135. for(j=0; j<n+2; j++)
  136. Edge[i][j].c=Edge[i][j].b=Edge[i][j].f=Edge[i][j].no=inf;
  137. for(i=1; i<=m; i++)
  138. {
  139. scanf("%d%d%d%d",&u,&v,&b,&c);
  140. Edge[u][v].b=b;
  141. Edge[u][v].c=c;
  142. Edge[u][v].f=0;
  143. Edge[u][v].no=i;
  144. }
  145. accompany();
  146. }
  147. return 0;
  148. }

猜你在找的React相关文章