NOIP 提高 2017 第一轮 第 22 题：如下图所示，A到B 是连通的。假设删除一条细的边的代价是1，删除一条

题目

如下图所示，$A$ 到 $B$ 是连通的。假设删除一条细的边的代价是 $1$，删除一条粗的边的代价是 $2$，要让 $A,B$ 不连通，最小代价是（）（2 分），最小代价的不同方案数是（_）（3 分）。（只要有一条删除的边不同，就是不同的方案）

答案

4; 9

题解

考点定位

图的最小割及最优方案计数。

解题过程

删除一些边使A、B不再连通，总代价最小的问题就是求最小割。按原图给每条细边赋代价1、粗边赋代价2，枚举删边集合并检查A、B的连通性，得到最小代价4，恰好有9个不同的删边集合达到该代价。

可用另一种方式交叉验证：枚举A、B分居两侧的顶点划分，计算跨两侧的边集，并按实际边集去重；得到的最小代价与方案数仍为4和9。

答案：4；9。

易错提醒

方案按删去的边集计数，同一边集不能因不同的顶点划分重复计数。