①求最小割边数:
把第一遍dinic之后把网络中满流量(残量为0)的边的残量改为1,其余的边残量改为无穷大,不含反向边。再跑一次dinic即可得出答案
②最小割边一定是满流的。
③给定一个图,求有多少边增大流量可以使得从源点到汇点流量增大
其实就是求最小割的割边是那些。
我们先求一次网络流,之后在残余图的基础上,从源点dfs一次,记录所有原点可以到达的点。
在从汇点dfs一次,记录所有汇点可以到达的点。
如果一条边左边是源点可以到达的,右边是汇点可以到达的,那么这条边就是割边,这条边容量加大,总容量就会变大
④
最小割判定是否唯一:
1,先跑一次最大流,得到残量网络;
2,在残量网络中沿着未满流的边查找,统计A能达到的点数sum1和
能达到B的点数sum2;
3,若sum1 + sum2 = N – 2则说明最小割唯一,反之不唯一。