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

[Mr.K 018]

第13期——

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

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

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

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

 

召唤阵：

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

[yhz012]

是图论问题

 

对问题数学建模

剧透

 

先从最简单的情况入手好了，已知（二维平面上）一堆点与点之间的距离，选择一组（无向）边使得任意两点间存在路径，且代价最小，所得结构为最小生成树 —— 引理1

首先可以证明最小生成树满足任意两点间有路径，需要证明该结构保证权重最小

假设有n个点，则无论怎么选，如果少于n-1条边，必然存在至少一组点之间没有路径

反之大于n-1条边，必然存在一条多余的边可以丢掉（因为构成了环）

因此只需要考虑n-1条边情况，根据最小生成树定义的最小，成立。

 

接下来就是开始考虑题目中的骚扰问题了

因为骚扰，所以某一条边的代价增加了，这时候我们需要找到新的最小生成树

 

因此整道题可以数学地表述为：

已知图 G = (V, E)，与（非负）权重w，现有一条边e 的权重增加从 w(e) 变为 w(e) + dw，如何快速求新的最小生成树

 

 

暴力的不能更暴力的方法

剧透

 

显然最暴力的方案是直接把e的权重换了，然后在新的权重上重跑一次最小生成树的算法就完了，所以用Prim花费O(n^2)带走就好了

注：Kruskal复杂度是O(m log m)，根据题意是完全图，m = O(n^2)，所以还是直接用Prim快一些

 

 

一些优化方法的想法

剧透

 

当然显然我们其实可以不必这么暴力

假如我们在原图上已经求到了最小生成树，因为只增加了一条边的权重，所以我们可以具体情况具体分析

1. 如果这条边本身就不在原来的最小生成树里面，那……？

2. 如果这条边在原来的最小生成树里面，但是只增加了0.0000000000000000001的权重，那……？

3. 考虑与上面这条相反的情况，假如这条边加了无限多的权重，你就当这条路了被毁了，这个情况下要如何做？ （注：最坏情况下可能并不会比暴力的速度更快）

 

感觉没人继续挑战，那我写完吧

剧透

 

显然情况1的情况下，我们本来就不要这条边，那自然现在代价更大了我们更不要了，所以最小生成树不变

而在我们需要用这条边的情况下，丢掉这条边我们会得到2个不联通的树，接下来只要我们在其中连一条边即可完成，显然应该选择其中最小的边。如果增加权重的这条边位置比较好，形成一侧比较少的节点（极端情况只有1个点），那我们只需要O(n)的时间比较所有连接到这侧的边的权重即可。但是如果脸不是很好，最坏情况下得到了两个n/2的树，那么我们不得不花费 n^2 / 4 = O(n^2)的时间比较之间的所有边，还是比较疼的。

 

 

 

更有趣的一些情况

剧透

 

假设现在战争情况好转，敌军开始撤退。具体来说，现在某一条路上的游击队减少了，因此我们可以减少这条路的守卫，这个情况下，怎么做最好？

即，与题目情况相反，不是增加某一条路的权重而是减少某一条路的权重，这时候最小生成树要怎么找

 

解答

剧透

 

类似的，如果降低了一条本来就在最小生成树的边的权重，那么再好不过了，最小生成树不变。

反之如果降低了一条树外的边，那么考虑把这条边加入树，则必然构成一个环。接下来只需要在这个环上把最重的边再丢出去即可，这个情况下最坏只需要O(n)的时间，实际上是比增加权重的情况要简单的

 

 

 

四月 23, 2020，由yhz012修改

[Mr.K 018]

1 小时前, yhz012 说道:

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

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

[yhz012]

刚刚, Mr.K 018 说道:

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

实际上就是这样，最坏还是O(n^2)，不过常数项来说还是比暴力重做要好多了

[Muriya Tensei]

依然满头问号(因为其实还没有学算法，只能来单纯头脑风暴）

（如果说前面有几期还能有点想法的话，后面的emm看不懂题）

 

----------------

半年过去了，现在已经能看懂并且知道怎么做出来了，时间过得真快（9.19）

九月 19, 2020，由Muriya Tensei修改