【模板】Stoer-Wagner算法

题目描述

定义无向图 $G$ 的最小割为:一个去掉后可以使 $G$ 变成两个连通分量,且边权和最小的边集的边权和。 给出一张无向图 $G$,求其最小割。

输入输出格式

输入格式


第一行,两个数 $n,m$,表示点数与边数。 接下来 $m$ 行,每行三个正整数 $a_i,b_i,w_i$,表示 $a_i$ 到 $b_i$ 有一条边权为 $w_i$ 的边。

输出格式


一行,一个整数表示 $G$ 的最小割,如果图不联通,请输出 `0` 。

输入输出样例

输入样例 #1

4 6
1 2 5
1 3 1
2 4 1
3 4 2
2 3 1
1 4 2

输出样例 #1

4

说明

对于前 $20\%$ 的数据, $n\leq 10$。 对于前 $40\%$ 的数据, $n\leq 100$。 对于另外 $10\%$ 的数据,保证输入为一棵树。 对于另外 $10\%$ 的数据,保证输入为一条链。 对于 $100\%$ 的数据, $n\leq 600,m\leq \frac{n\times (n-1)}{2}$ ,保证 $\sum_{i=1}^{m}w_i \leq10^9$ 。 #### PS:想交 最大流/最小割树 的就省省吧。