最小割问题

  • Post author:
  • Post category:其他


①求最小割边数:

把第一遍dinic之后把网络中满流量(残量为0)的边的残量改为1,其余的边残量改为无穷大,不含反向边。再跑一次dinic即可得出答案




②最小割边一定是满流的。











③给定一个图,求有多少边增大流量可以使得从源点到汇点流量增大




其实就是求最小割的割边是那些。



我们先求一次网络流,之后在残余图的基础上,从源点dfs一次,记录所有原点可以到达的点。



在从汇点dfs一次,记录所有汇点可以到达的点。



如果一条边左边是源点可以到达的,右边是汇点可以到达的,那么这条边就是割边,这条边容量加大,总容量就会变大






















最小割判定是否唯一:



1,先跑一次最大流,得到残量网络;



2,在残量网络中沿着未满流的边查找,统计A能达到的点数sum1和



能达到B的点数sum2;



3,若sum1 + sum2 = N – 2则说明最小割唯一,反之不唯一。







版权声明:本文为Little_boy_z原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。