Codeforces 847J Students Initiation 二分答案 最大流

Codeforce 847J Students Initiation

题意

给一个包含$n$($n \leq 5000$)个点的无向图,边的条数$m \leq 5000$,没有重边自环。现在给每条边一个方向,问每个点的出度的最大值,最小为多少。输出这个最小值,并输出方案。

思路&建图

  1. 看到最大值最小,最小值最大,首先想到炸天哥猜想:二分!!
  2. 二分这个最大值$mid$,检验这个猜测值是否满足要求
  3. 从源点相这$n$个点引一条边,容量为$mid$。
  4. 对于第$i$条边来说,其编号为$n+i$,从其两个断点分别引一条边到这个点,容量为$1$。再从这个点到汇点连一条边,容量为$1$。
  5. 跑最大流,如果最大流和边的数目相同,即这个猜测值可行。此时,对于每一条边对应的点来说,这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。

代码

 

 

HDU 6214 Smallest Minimum Cut 最小割的割边的数目最少

Smallest Minimum Cut

题意

给一个有向的网络图,每条边有一定的容量$w_i$,现在以$1$点为源点,$n$点为汇点。求一组最小割的割边,使边的数目最少,输出最少数目。

建图&思路

直接按照原网络建图,只是边的容量改变为$10000 * w_i +1$,其中边的条数$m<10000$。这样跑最大流(最小割)后,假设最大流为$flow$,那么$flow / 10000$就是原始网络的最大流(最小割),$flow \mod 10000$就是最小割的最少边的条数。

代码

 

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模板,所以不怎么好看。