[AHOI2009]最小割

给你一个有流量的图,求最小割的可行边和必经边。


先跑最小割,然后剩下一个残余网络。

可以思考一件事情,满流的边是什么呢?

显然一次网络流,满流的边会包含了所有的最小割。

按照残余网络跑SCC。

如果对于一条满流的边边,我们考虑如果他的两个点存在于同一个SCC中的话,那么这条边肯定不会作为任意一个最小割的方案,因为如果存在于同一个SCC说明至少有一条流量为1的增广路可以走,那么此时如果他存在于某一组方案中,不如把这条边去掉更优秀。

对于一条满流的边如果起点和S属于同一个SCC,并且终点和T属于同一个SCC,则这条边是必经边。

增加一条边的流量,如果最小割增加,说明一定在最小割中。

可以发现S到u一定有一条增广路,v到T有一条增广路,则此时这条边增加,最大流也会增加,最小割也会增加。

原文地址:https://www.cnblogs.com/xgcxgc/p/13032475.html