最小割

悲催的最小割之路

无向图的最小割,几百年前就干过的事情。一直以来Stoer-Wagner算法一条路撸到黑。ACM集训队留下来的代码也是百试不爽。偶然间听说一种算法叫做Karger的也可以处理最小割问题。姑且拿来写一写试试看了。
最大流算法除外,其实目前看到的最小割算法都是基于把点粘合在一起来计算的。
先上传统Stoer-Wagner算法。

##Stoer-Wagner##
这是一个神奇的算法。复杂度O($n^3$)。它利用最大生成树的原理来处理数据。算是有步骤地一步一步的找到该合并的点。具体操作如下
这个算法的关键在于一个定理,叫做“很简单的以至于不知道名字的定理”,如下:
在这个图中设定一个源点s,汇点t。假设我们现在已经求得了最小割
1,s,t两个节点分别在最小割后节点集的两部分,那么s-t的割就是最小割了
2,s,t两个节点都在最小割后节点集的一边,那么s-t合并之后,并不影响最小割的下一步求解
基于这个理论,我们可以得出一个算法的关键结论:
每次定义一组s,t。求出s-t的割,记录这个割,然后合并s-t。合并后我们就剩下n - 1个点。然后继续定义新的s-t。如果新的s-t的割小于原来的割,那么就更新最小割,继续合并新的s,t……直到最后变成两个点。
这样做可以照顾以上两点。因为如果每次操作s-t的时候,如果s-t确实是最后的割,那么我们记录了这个割。如果不是,那么我们合并继续。所以这个算法一定是对的。

那么问题来了,怎么求s-t的割呢?
分成两个子问题。如果指定了s-t,我们可以使用最大流的各种算法来求出。但是现在没有指定s-t,我们可以在点里边任意选择s-t嘛。所以就引申出来一个算法,最大生成树。

结论是这样的

利用prim算法求最大生成树,每个节点不断的加入到图中,最后加入的两个节点之间的割,就等于最后一个加入节点距离源点的距离。也就是把倒数第二个加入的节点当作s,最后一个节点当作t,这个割就是最后一个节点的距离数

证明

我也不知道

PS:这个证明我还在咨询大神,弄懂了再来更新
具体的算法操作代码放在最后。

##Dinic##
也就是最大流啦。复杂度O($n^3$m)一个很著名的定理,最大流就是最小割。所以如果指定了最大流的源汇点,使用诸如SAP,Dinic等等的算法求出最大流,得到的结果就是最小割。
但是如果要求全局最小割呢,就需要枚举汇点了。不过上边的Stoer-Wagner算法有说,找到的源汇点是可以合并的。所以我们可以在每次Dinic求完最小割之后合并,再继续求下一个过程。复杂度可以显著降低。不过我觉得没必要了。还麻烦,直接枚举汇点好了。
这种算法真的是没啥意思的,复杂度高还难写,为啥不用Stoer-Wagner呢,好写高效
其实最大流算法和Stoer-Wagner的算法的最大区别在于,Stoer-Wagner使用了这个问题可以自己指定源点汇点的特点,方便的自行指定求出源汇点的割。最大流则是被动指定。效率肯定比不上Stoer-Wagner了。

代码放在最后了啊

##Karger##
这是一个神奇的算法!
说它神奇,是因为它简单。
说它神奇,是因为它复杂。
说它神奇,是因为这个算法太矛盾了。
话说当年Karger大牛在读博士的时候灵机一动,想出了这个空前绝后超级简单的算法。以至于后人无法再直视Karger。
这个算法的理论复杂度是O($n^2ln^{O(1)}n$),但是写出来后就不是这样的了。
首先这个算法是这样的。还是借用上边Stoer-Wagner的合并操作说明。Stoer-Wagner是找到s-t后合并s-t,但是Karger是在每次过程中,随机找一条边的两个点来合并。然后不断合并合并直到剩下两个点为止。然后这两个点中间的边就是最后的割了。这个割当然不一定是最小割。但是我们可以试嘛。论文说试上$n^2$次就可以达到满意的结果了。成吧。写写试试看?
本来这个算法很早就发明了。为啥到现在应用都不广泛呢?其中必有原因。写写后发现。实际上的复杂度要高得多。
$n^2$的迭代次数暂且不说。就说我们“随机取一条边”这个问题。如果我们用邻接表来存放数据点,那么随机取边就需要O(n)的复杂度了。因为毕竟我们要遍历嘛。如果用邻接矩阵来存放呢?我们需要不断的尝试边,然后看看有没有可用边。这个就看是稀疏图还是稠密图了。稀疏图就惨了,稠密图还好。
各种纠结,参考网上大牛代码后,决定用邻接表了。
优化了很久,发现不论如何,随机找边这个操作也在O(n)上,合并也几乎是O(n)。同时为了快速我用的指针,内存泄漏问题也不容忽视。同时中间还有无数个操作需要寻找一个点的位置。这种事情又是O(n)了。大体看了一下,如果是稠密图,因为我们每次迭代前都需要重新更新一下图数据,几乎是需要O($n^4$)的。。。

代码细节:
邻接表中,每个点节点VNode存放的是每个节点,后边跟的一串是这个节点相连的边
每个ENode就是VNode连接的节点
所以这是一种看起来复杂度很低,实际上写起来微小操作特别耗时的算法。几乎还是不如Stoer-Wagner。
代码放在最后。。。

##代码区域##
输入实例,完全按照邻接表的形式输入。不知道什么叫做邻接表的,看看这个实例也就懂了
每行的第一个数字,也就是VNode,表示这一行表示的点的标号
后边跟的一串是这个节点相连的边

###input###

1
2
3
4
5
0 1 2 3
1 0 2 3
2 0 1 3 4
3 0 1 2 4
4 2 3

代表的图形是这样的
代表图

Contents
,