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. 跑最大流,如果最大流和边的数目相同,即这个猜测值可行。此时,对于每一条边对应的点来说,这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。

代码

 

 

发表评论

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