NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 22 题

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

这题本质是求带权最小割，但不用建图跑算法。拿到图先别急着算，脑子里过一遍所有从A到B的路：有几条细边路、几条粗边路，再想能不能用几条细边就把它们全拦死，或者几条粗边更省。

最容易掉进两个坑：一是把粗边当1算，以为删一条粗边就能切断所有路，结果最小代价算成2或3；二是只盯着某一条路想怎么断，忘了要同时切断所有路。比如有人会把两条粗边都删了（代价4）就以为够了，其实还有一条细边路没断。还有人会数方案时把“删哪条边”和“删哪些边”搞混，以为删同一条边不同顺序算不同方案，记住只要边集不同才算不同。

这道题考查的是图论中的带权割（minimum cut）概念，只不过题目把割的代价拆成了细边1、粗边2，要求切断所有从A到B的路径。命题人喜欢在这种填空题里挖坑：让你以为只要删几条粗边就能搞定，其实还有一条细边路；或者让你以为删一条边就能切断所有路，结果漏了另一条路。所以解题心法是：先枚举所有A→B的路径，看它们由什么边组成，再想怎么用最少的代价把这些路全拦下来。具体到这张图，从A到B一共有三条路：两条是只经过细边的路，一条是只经过粗边的路。因为粗边代价2，删一条粗边就能把那条路切断，代价2；但剩下的两条细边路还得各删一条细边，每条代价1，所以总代价是2+1+1=4。有没有更省的办法？试着删两条粗边（代价4）能不能同时切断所有路？不行，因为两条细边路根本没碰粗边，删粗边对它们无效。删三条细边（代价3）呢？也不行，因为那条粗边路还通着。所以最小代价确实是4。接下来数方案：删那条唯一的粗边有1种选法；两条细边路各选一条删，有2×2=4种选法；把粗边和一条细边组合，有1×2=2种；把粗边和两条细边组合，有1×1=1种。加起来1+4+2+1=9种不同方案。易错点在于：有人会以为删粗边就能切断所有路，把代价算成2；或者只盯着某一条路想怎么断，忘了要同时切断所有路；还有人在数方案时把“删哪条边”和“删哪些边”搞混，以为删同一条边不同顺序算不同方案，记住只要边集不同才算不同。从考频看，带权最小割这类题在NOIP提高组初赛近五年出现频率不高，但一旦出现就是重头戏，通常结合具体图形考察枚举和组合计数，难度中等偏上。未来预测：命题人可能会继续用这种“带权割+组合计数”的形式，或者换成更复杂的图结构（比如多条粗边、多条细边交织），但核心思路不变——先找所有路，再算最小代价组合，最后数方案数。暂无足够依据预测具体变体。