yhz012 发布于四月 23, 2020 分享 发布于四月 23, 2020 (已修改) 是图论问题 对问题数学建模 剧透 先从最简单的情况入手好了，已知（二维平面上）一堆点与点之间的距离，选择一组（无向）边使得任意两点间存在路径，且代价最小，所得结构为最小生成树 —— 引理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修改 1 链接到点评
yhz012 发布于四月 23, 2020 分享 发布于四月 23, 2020 刚刚, Mr.K 018 说道: 考虑一个想法：决定弃用一个已使用的道路，无非是将原有的最小生成树砍成两半，找一条边接上即可 实际上就是这样，最坏还是O(n^2)，不过常数项来说还是比暴力重做要好多了 yhz012遇见阿里尼，决定跟着他学打游戏，买游戏被G胖骗走了 -2节操 链接到点评
推荐贴