经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
Codeforces Round #304 (Div. 2)(CF546E) Soldier and Traveling(最大流)
来源:cnblogs  作者:swineherd_MCQ  时间:2019/9/26 8:53:18  对本文有异议

题意

给定 n 个城市,m 条边。人只能从走相邻边相连(只能走一次)的城市。
现在给你初始城市的每一个人数,再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能,输入“YES”并输出方案,不能则输出“NO”。

http://codeforces.com/contest/546/problem/E

思路

当∑a!=∑b时,肯定不能。

建一个超级源点s和超级汇点t,s到(1~n)连一条容量为a[i]的边,(n+1~2*n)到t连一条容量为b[i]的边,再将图中给定相连的边连容量为inf的边,比如u和v相连,那么u到v+n和v到u+n都要连容量为inf的边。还要将自己跟自己连边,即i到i+n连一条容量为inf的边,因为自己点的人不走相当于自己点走到自己点。最后都连上反向边用Dinic跑最大流,如果最大流==∑a,那么能,方案可以根据i到i+n的反向边的流量来求解。

样例的建图类似下面这样(随便画的):

代码

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<queue>
  5. using namespace std;
  6. const int inf=1e9;
  7. const int N=505;
  8. int n,m,x,y,z,maxflow,deep[N];//deep深度
  9. struct Edge
  10. {
  11. int next,to,dis;
  12. } edge[N*10];
  13. int num_edge=-1,head[N],cur[N];//cur用于复制head
  14. queue <int> q;
  15. void add_edge(int from,int to,int dis,bool flag)
  16. {
  17. edge[++num_edge].next=head[from];
  18. edge[num_edge].to=to;
  19. if (flag) edge[num_edge].dis=dis;//反图的边权为 0
  20. head[from]=num_edge;
  21. }
  22. //bfs用来分层
  23. bool bfs(int s,int t)
  24. {
  25. memset(deep,0x7f,sizeof(deep));
  26. while (!q.empty()) q.pop();
  27. for (int i=0; i<=2*n+1; i++) cur[i]=head[i];
  28. deep[s]=0;
  29. q.push(s);
  30. while (!q.empty())
  31. {
  32. int now=q.front();
  33. q.pop();
  34. for (int i=head[now]; i!=-1; i=edge[i].next)
  35. {
  36. if (deep[edge[i].to]>inf && edge[i].dis)//dis在此处用来做标记 是正图还是返图
  37. {
  38. deep[edge[i].to]=deep[now]+1;
  39. q.push(edge[i].to);
  40. }
  41. }
  42. }
  43. if (deep[t]<inf) return true;
  44. else return false;
  45. }
  46. //dfs找增加的流的量
  47. int dfs(int now,int t,int limit)//limit为源点到这个点的路径上的最小边权
  48. {
  49. if (!limit || now==t) return limit;
  50. int flow=0,f;
  51. for (int i=cur[now]; i!=-1; i=edge[i].next)
  52. {
  53. cur[now]=i;
  54. if (deep[edge[i].to]==deep[now]+1 && (f=dfs(edge[i].to,t,min(limit,edge[i].dis))))
  55. {
  56. flow+=f;
  57. limit-=f;
  58. edge[i].dis-=f;
  59. edge[i^1].dis+=f;
  60. if (!limit) break;
  61. }
  62. }
  63. return flow;
  64. }
  65. void Dinic(int s,int t)
  66. {
  67. while (bfs(s,t))
  68. maxflow+=dfs(s,t,inf);
  69. }
  70. int a[N],b[N];
  71. int main()
  72. {
  73. memset(head,-1,sizeof(head));
  74. scanf("%d%d",&n,&m);
  75. int s1=0,s2=0,s=0,t=2*n+1;
  76. for(int i=1; i<=n; i++)
  77. {
  78. scanf("%d",&a[i]);
  79. add_edge(s,i,a[i],1);
  80. add_edge(i,s,a[i],0);
  81. s1+=a[i];
  82. }
  83. for(int i=1; i<=n; i++)
  84. {
  85. scanf("%d",&b[i]);
  86. add_edge(i+n,t,b[i],1);
  87. add_edge(t,i+n,b[i],0);
  88. s2+=b[i];
  89. }
  90. for (int i=1; i<=m; i++)
  91. {
  92. scanf("%d%d",&x,&y);
  93. add_edge(x,y+n,inf,1);
  94. add_edge(y+n,x,inf,0);
  95. add_edge(y,x+n,inf,1);
  96. add_edge(x+n,y,inf,0);
  97. }
  98. if(s1!=s2)
  99. {
  100. puts("NO");
  101. return 0;
  102. }
  103. for(int i=1;i<=n;i++)
  104. {
  105. add_edge(i,i+n,inf,1);add_edge(i+n,i,inf,0);
  106. }
  107. Dinic(s,t);
  108. // cout<<maxflow<<endl;
  109. if(maxflow==s1)
  110. {
  111. puts("YES");
  112. int g[N][N];
  113. for(int i=1;i<=n;i++)
  114. {
  115. for(int j=head[i];~j;j=edge[j].next)
  116. {
  117. int v=edge[j].to;
  118. if(v>n)
  119. {
  120. g[i][v-n]=edge[j^1].dis;
  121. }
  122. }
  123. }
  124. for(int i=1;i<=n;i++)
  125. {
  126. for(int j=1;j<=n;j++)
  127. {
  128. printf("%d ",g[i][j]);
  129. }
  130. puts("");
  131. }
  132. }
  133. else
  134. {
  135. puts("NO");
  136. }
  137. return 0;
  138. }

原文链接:http://www.cnblogs.com/mcq1999/p/TuLun_3.html

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号