小编ces*_*rbs的帖子

我需要在图表上找到最小切割.我一直在阅读关于流网络的内容,但我能找到的是最大流算法,如Ford-Fulkerson,push-relabel等.鉴于最大流量最小切割定理,是否可以使用其中一种算法来查找使用最大流算法在图表上的最小割数？怎么样？

到目前为止我发现的最好的信息是,如果我发现"饱和"边缘,即流量等于容量的边缘,那些边缘对应于最小切割.真的吗？这对我来说听起来不是100%.确实,最小切口上的所有边缘都将饱和,但我相信也可能存在饱和边缘,这些边缘超出最小切割"路径".