关于最小割的求解方法

由网络最大流最小割定理可以很容易的知道,最小割在数值上是等于最大流的。

【1】如果题目要求的是最小割的数值,那么只要跑一遍网络最大流即可得出答案。

【2】如果要求的是S集合和T集合,那么先跑一遍网络最大流,然后在跑完网络最大流的残留网络中,从源点Vs开始进行DFS,能遍历到的节点都属于S集合,最终,剩下的节点都属于T集合。

【3】如果要求的是最小割由哪些弧构成,那么可以在邻接表中寻找,一个点在S集合一个点在T集合的弧就是构成最小割的弧。

 PS:最小割中所有的前向弧在网络最大流中一定是饱和的弧,但饱和的弧不一定就是最小割中的弧。

原文地址:https://www.cnblogs.com/zufezzt/p/4679339.html