Stoer Wagner 算法
Stoer Wagner 算法主要是解决无向图最小割的问题。题目链接给定一张无向图，每一条边都有其花费，求最少能使这张图不连通应割掉的边数。 原作者论文，侵删解题思路首先我们可以使用网络流暴力跑，也就是随机一个源点然后枚举汇点跑最大流那种，但是时间复杂度有点高，上界是 $O(n^3m)$。于是 就有了 Stoer Wagner 算法来解决这个问题。我们先描述一下这个算法的一般流程： 1. $...
Stoer Wagner 算法主要是解决无向图最小割的问题。题目链接给定一张无向图，每一条边都有其花费，求最少能使这张图不连通应割掉的边数。 原作者论文，侵删解题思路首先我们可以使用网络流暴力跑，也就是随机一个源点然后枚举汇点跑最大流那种，但是时间复杂度有点高，上界是 $O(n^3m)$。于是 就有了 Stoer Wagner 算法来解决这个问题。我们先描述一下这个算法的一般流程： 1. $...