居然是硬枚举 s、t，o(N^5) 啊。。。。。。
于是就又写个了 Stoer-Wagner 算法介绍。。。。。。
这里原文照抄下吧。。。
其实话说我一开始也是最大流做滴。。。最大流即使是用hlpp也要 o(n^4) 的复杂度，要像某个题解说的枚举 s、t 就到 o(n^5) 了。。而且hlpp也不是随随便便就能写出来滴。。。
不过看清本质之后，这一题本质就是求无向图的全局最小割，这其实是有专门算法的，叫 Stoer-Wagner 算法，复杂度不超过 o(N^3)，而且代码行数很短。。真的很短
下面概略说明下算法，正确性证明略去：
首先我们定义对于不存在的边 (u,v)，w[u, v] = 0。
之后介绍经典的 Contract(a, b) 操作：
加入新点 u，对于 a、b 之外的每个点 v，加入无向边 (u, v) 并令 w[u, v] = w[a, v] + w[b, v]
完成之后删除 a、b 两点及相关联的所有边
不难看出，每做一次 Contract 操作，图的节点数减少1
Stoer-Wagner 算法的正确性基于如下定理：
一个无向图的全局最小割，等于这个图的 s-t 最小割，或对这个图进行 Contract(s, t) 得到的图的全局最小割。
定理是显然的，下面我们说明如何求无向图的 s-t 最小割：
首先定义对于点集 A 和点 u，w[A, u] 表示 A 中所有点与 u 连边的权值之和。再次说明，不存在的边视为0处理。
1. 初始化点集 A={}
2. 任意取一点 a 加入 A 中
3. 每次取 w[A, u] 最大的点 u，将其加入 A，直到 A=V
4. 可取3中倒数第二次加入的点为 s，倒数第一次加入的点为 t（无向图顺序无关紧要），则对应的 s-t 最小割为 w[U-{t}, t]
证明可以用数学归纳法，大家自己试试吧^_^
不难看出，上述 s-t 最小割算法的朴素实现是 O(N^2) 的（第三步显然还可以用最大堆优化，达到更好的时间界），而对于一个图，Contract 操作最多进行 n-1 次（此时图中只剩1个点了）。所以算法的复杂度不超过 O(N^3)
而代码行数，可想而知有多短了。。。
而且即使写错了什么，调试起来也比调试hlpp轻松多了
题目：
一个国家由n个城市组成，任意两个城市间都有一条双向的道路。如今，恐怖分子想要炸掉其中的一些道路，使得这n个城市变得不再连通，也就是说，存在至少两个城市，它们之间不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到它们的目的，所需要的最小总代价是多少。
