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$就是最小割的最少边的条数。

代码