BZOJ 2229 [Zjoi2011] 最小割

发布于 2017-06-27  212 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2229

题意:对于无向网络图的所有点对 (s,t),求满足 s-t 割不超过 x 的点对的总个数...


暴力需要枚举点对做\(n^2\) 次最大流,复杂度为\(O(n^6)\),完全无法接受...

有一个性质:一个无向图本质不同的最小割只有\(n-1\) 种。那么可以据此构造一个很有趣的东西叫等价流树,它是一棵具有如下性质的树:

原图中两个点的最小割的权就是等价流树上对应链上的最小边权。

这个时候有一个小问题... 如何证明上述性质的正确性呢?它的证明是复杂的(以蒟蒻的方法,就先不贴出来了... 欢迎路过神犇给予较好的方法

那么我们考虑如何构造等价流树,普遍的,使用 Gusfield 算法来解决这个问题,它是一个基于分治策略的算法:

首先,对点集合分治,设当前处理点集为 W

从 W 中随意选择两点 s,t,在原图中求出 s-t 的最小割,在等价流树中为 s,t 连边,权值为该最小割权值

对于得到的 s 割和 t 割,可以证明是可以做到互不影响的,递归进行以上操作,直至点集中只有一个点

关于算法正确性的证明会后补... 那么问题就解决了...

 

 


一个非常弱的准退役OIER