最小割树=分治+最小割

针对的是无向图。(第一次写的时候,反向边下意识容量写为了0,WA)

其实不要被最小割树这个名词吓到。。

首先要知道,任意两点之间的最小割,不同的只有n-1个。(知道就好啦,证明什么的不会QAQ

那么构建最小割树的流程是这样的:

1.集合中随便找两个点,求这两点的最小割

2.用求出的最小割更新s,t两个集合之间点的最小割(或者可以直接建边,那么最终两点之间的最小割就是两点之间路径的最小权值

3.对s,t两个集合递归处理

其实是非常easy的一个东西,知道性质就行了。

题目:ZJOI2011最小割 ,CQOI2016最小割

原文地址:https://www.cnblogs.com/wjyi/p/5669773.html