RainAir
My OI Blog
RainAir
Stoer Wagner 算法

Stoer Wagner 算法主要是解决无向图最小割的问题。

题目链接

给定一张无向图,每一条边都有其花费,求最少能使这张图不连通应割掉的边数。
原作者论文,侵删

解题思路

首先我们可以使用网络流暴力跑,也就是随机一个源点然后枚举汇点跑最大流那种,但是时间复杂度有点高,上界是 $O(n^3m)$。

于是 就有了 Stoer Wagner 算法来解决这个问题。

我们先描述一下这个算法的一般流程:
1. $min = INF$,固定一个顶点 $P$
2. 从点 $P$ 用 “类似” prim 的算法扩展出 “最大生成树” ,记录最后扩展的顶点和最后扩展的边
3. 计算最后扩展到的顶点的切割值(即与此顶点相连的所有边权和),若比 min 小更新 min
4. 合并最后扩展的那条边的两个端点为一个顶点(当然他们的边也要合并,这个好理解吧?)
5. 转到 $2$,合并 N-1 次后结束
6. min 即为所求,输出 min
相信大家看到这里一定是懵逼的…那么建议大家先阅读代码,然后结合论文食用。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/392
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

Stoer Wagner 算法
Stoer Wagner 算法主要是解决无向图最小割的问题。 题目链接 给定一张无向图,每一条边都有其花费,求最少能使这张图不连通应割掉的边数。 原作者论文,侵删 解题思路 首先我们可以使…
扫描二维码继续阅读
2018-12-25
标签
近期评论