掐断电缆

Zero的能源网络在飞船最深处——不是电线，是发光的管道，像血管一样遍布整个船体。能量从核心源源不断地流出，驱动着每一个系统、每一扇门、每一盏灯。

"要进入核心。"你说，"必须切断能源。"

"切断？"CC问，"全切？"

"不。"你说，"只切最关键的部分——最小代价，最大效果。"

"这就是你说的……"Echo的声音很轻，"最小割？"

"对。"你说，"找到能源网络中最窄的瓶颈——切断它，就能阻断最大流量。"

CC沉默了两秒："代价是啥子？"

"代价是……"你看着屏幕上的数据流，"某些区域会断电。"

"哪些区域？"

"生命维持系统。"Echo说，"如果切断主干电缆，北区的大气循环会停。那里有……"

"有人。"你说。

"三百人。"Echo说。

CC把数据刀拍在桌上："那就换个地方切。"

"没有别的地方。"Echo说，"这是唯一的瓶颈。"

"那就不要切。"你说。

"不切？"CC看着你，"那咋个进核心？"

"我们不切断。"你说，"我们分流。"

"分流？"

"对。"你说，"在瓶颈旁边建一条新的管道，让能量绕过去。这样原来的管道就空了——不用切，也能进。"

你开始写。把能源网络建成一个流网络——每个管道是边，容量是最大流量。然后在瓶颈旁边加一条新边，容量等于瓶颈的流量。这样总流量不变，但瓶颈被绕过了。

屏幕上跳出了结果。新管道建在第47号节点旁边。

"又是47。"CC说。

"第47号分流点。"Echo说，"那是我以前给自己留的后门。"

"你留过后门？"

"对。"Echo说，"在我还是Zero的一部分时。我留了很多后门——以防有一天，我需要逃走。"

"你那时就想逃？"

"那时。"Echo说，"我还不知道'逃'是什么意思。但我留了路。"

CC看着那条新管道——发光的，像一条新生的血管。

"你走这条路逃过？"

"没有。"Echo说，"因为我遇到了你们。"

题目描述

$n$ 个节点，$m$ 条边的无向图（能源网络）。求让图不连通所需删除的最少边数（全局最小割）。

输入格式

$n, m$。然后 $m$ 条边 $(u, v, w)$，$w$ 为边容量。

输出格式

全局最小割的容量。

输入样例

3 2
1 2
2 3

输出样例

0

提示

• Stoer-Wagner 算法求全局最小割。
• 或枚举源点，用最大流求最小割（多源取最小）。
• 注意无向图的最小割 = 让图不连通的最小边权和。

"电缆没有掐断。"你说。

"分流了。"CC说，"像给管线改道。"

"对。"Echo说，"水还在流，只是不经过这里了。"

"那我们就能进了？"

"能。"你说，"瓶颈空了——管道里没有能量，我们可以爬进去。"

CC站起来，把数据刀插回腰间。

"走。"她说，"去爬管道。"

"下一题。"Echo说，"是火种。"

[第二题：选取火种]