娱乐 每 日 算 法 挑 战 【第D期】

[Mr.K 018]

第13期——

本题来源：HDU4126，题意复述如下：

现有n个据点，两两之间连有道路。现在要在一些道路上驻扎守卫，使得任意两个据点之间都可以或者直接或者间接地传递消息（消息只能在有守卫驻扎的道路上才能传递，否则会丢失或者被截获）。已知每条道路需要的守卫数量。

现在得到情报，有一条道路上会发生游击队袭扰，受到影响的道路需要增派守卫来保障消息的安全传递。当然，也可以不再用这条道路，换用其他的道路驻扎守卫。现在尚不清楚游击队具体会在哪条道路上进行袭扰，只能大致圈定可能发生袭扰的范围。同时，我们知道如果在某个地方发生了袭扰时需要增派的守卫数目。如前所述，游击队袭扰同时只会发生在一条道路上。

现在已知每条道路所需的守卫数量和游击队可能的袭扰情况（多种可能，每种都会注明发生的道路和需增派的兵力。同一条道路上的袭扰所需的增派兵力时可能不同的，它们视为不同的可能性）。问，在每种情况下所需的最少守卫数量是多少？

 

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

[Mr.K 018]

1 小时前, yhz012 说道:

你就当这条路了被毁了，这个情况下要如何做

考虑一个想法：决定弃用一个已使用的道路，无非是将原有的最小生成树砍成两半，找一条边接上即可