Codeforces 546E Soldier and Traveling 最大流找可行方案

Codeforces 546E

题意

一个国家有$n$个城市,由$m$条双向边连接。现在,每个城市有$a_i$个士兵。现在每个士兵可以沿着一条边,走到相邻的城市,并且只能走一次,或者不走,留在原来的城市。问能否达到每个城市分别有$b_i$的士兵。切每条道路有一个上限,通过的士兵的个数不能超过这个上限。

  • 如果可以,输出"YES"。并输出方案,用矩阵$A_{ij}$表示从$i$城市走到$j$城市的士兵的个数。
  • 如果不可以,输出"NO"。

建图&思路

  1. 左边$n$个点,从源点往分别这$n$个点引一条边,容量为$a_i$。
  2. 右边$n$个点,从这个$n$个点分别往汇点引一条边,容量为$b_i$。
  3. 对于每一个城市$i$来说,从左边的第$i$个点向右边的第$i$个点引一条边,容量为$INF$,表示允许驻留。
  4. 对于每一条路来说,它的两个断点分别为$st,en$,那么需要从左边的第$st$个点引一条边到右边的第$en$个点,容量为这条路的上限。同时,从左边的第$en$个点引一条边到右边的第$st$个点,容量为这条路的上限。表示这两个城市之间的士兵可以相互移动,数量的上限不超过路的上限。
  5. 跑最大流,得到最大流量为$flow$,如果$flow$和士兵的总数相同,那么就有可行方案。否则没有。
  6. 对于每一个左边的点,枚举每一条向右边连的边,那么从这个点对应的城市到所连的点的城市所移动的士兵的个数,就是这条边所流过的流量,即这条边反向边的残余流量。

代码

注释

这个代码是2015年写的isap模板,所以不怎么好看。

发表评论

电子邮件地址不会被公开。 必填项已用*标注