自选题解解题报告

1、 江苏省常州高级中学 刘启鹏Terrorist Attack题解报告Company Logo简要描述 一座国家有N个城市以及M条连接两个城市的双向道路。现在这个国家被笼罩在恐怖袭击的阴影下，然而恐怖分子只会攻击道路。作为恐怖分子头目的你想知道，对于Q条道路，如果把它摧毁后想要使得所有城市连通，所有道路的长度之和的最小值是多少（如果无法连通所有城市，输出”Not Connected”）。满足N=10000，M=100000，Q=100000，原图可能有出现两座城市之间有多条道路，可能出现一个城市有连接自己的道路时间限制：1s，空间限制32MB。Company Logo简要描述8371692191

2、1Company Logo算法分析与设计 读完题可以很快得到一个简单的模型：有一个N个节点M条边的无向图（可能有自环、重边），每次要求去掉一条边后原图的最小生成树（去掉的边在下一次询问时仍属于原图）。最容易想到的是朴素的模拟算法。每次把一条边去掉，做原图的最小生成树，然后输出答案或者判断图不连通。然而无论使用堆优化的prim算法还是kruskal算法，由于询问Q达到了100000次，复杂度分别将达到O(QNlogM) 和O(QMlogM)，想要AC此题无疑是不实际的。Company Logo算法分析与设计 我们无法使用自己所得心应手的算法来解决此题的原因是什么呢？因为我们要操作的模型是图，而图

3、的优美性质并不多，导致了我们开始无法顺利解决此题。而树却拥有许多优美的性质，而最小生成树更是有无数有趣的结论和特点。我们不妨换一个角度来思考问题，化麻烦的图为简洁优美的最小生成树来考虑。 83716921911Company Logo算法实现 一个很直接的想法是把原图的最小生成树求出来，再把删除边化为对树的操作。我们将一步一步，利用最小生成树的特点来解决这个问题。把原来的最小生成树求出来以后，显然只有删掉树上的边才会使答案改变。而删掉一条树边后，由Kruskal算法的性质我们容易知道树上的其他边在最终解中保持不变。因此删边后树被分成了两个点集，我们的目标就是在这两个点集间找一条权值最小的边构成

4、新的最小生成树。Company Logo算法实现83716921911Company Logo算法实现算法1：求出最小生成树，对于每一个删除边的询问，利用并查集将点集分为两部分，再枚举边；对于所有跨越两个不同点集的边，寻找一条最小的。时间复杂度：O(MlogM+Q*(N+M)空间复杂度：O(N+M)Company Logo算法实现 这样简单的改进后，我们就将原来枚举的复杂度的log因子去掉了。虽然这个算法的时间复杂度仍然不令人满意，不过我们已经看到了成功的曙光了。继续思考我们刚才的算法时间复杂度不能令人满意的原因。对于一次删除操作后，原树的形态只有很小的改变，而我们却将原树完全重新构造了出来；

5、而且在枚举边的过程中，也出现了很多冗余。能够如何改进呢？Company Logo算法实现 我们把原图中除最小生成树以外的边叫做“待用边”，上文我们尝试每次删掉树边，在待用边中寻找一条连接两点集且最小的边，但这一步难以实现。我们能否反过来想：找出每条待用边能对哪些树边产生影响。有了这样的思路，我们不难发现把一条待用边加进原最小生成树后都会形成一个环，正是环上的树边会被这条待用边影响。由于每个环与原MST的交都是树上的一条路径，于是我们得出了如下算法：构建了MST后，对于图的其他边(X,Y)，用Length(X,Y)更新树上的路径(X,Y)中的所有树边；每条树边取最小的更新值作为答案。到了这一步，

6、问题又化归为树上的路径问题，利用边的DFS序列或路径剖分等想法又一下涌现了出来。Company Logo算法实现316Company Logo算法实现 算法2：求出最小生成树，对于每一条连接u,v的非树边，更新u到v的路径上所有树边，利用树链剖分或者动态树得以实现。树链剖分：时间复杂度：O(MlogM+Mlog2N+Q)空间复杂度：O(N+M)动态树：时间复杂度：O(MlogM+MlogN+Q)空间复杂度：O(N+M)Company Logo算法实现 看起来这题已经能够十分出色的解决了，然后似乎我们还能够改进和优化，我仍然不能满意于当前的算法。树链剖分的复杂度有log2N的因子，稍不注意常数就

7、会导致超时；而动态树又是比较难实现的东西，容易写错且常数也很大。实验证明，以上两种算法即使经过很好的优化在在线评测时仍然是超时。Company Logo算法实现 由于这题并没有要求在线回答询问，而我们第一步解决更新树边的时候是无序的，导致了我们必须借助高级数据结构来高效的维护。如果我们对于非树边进行排序呢？我们惊讶地发现，我们完全不需要多么高深的数据结构了，仅仅是一个一维数组就可以解决这个问题。定义Length Length(u,v)i为边(u,v)i的长度我们只需按照Length(u,v)i从小到大枚举边进行更新，并且保证每条边只被更新一次即可。对于一条非树边u,v，求出LCA(u,v)，然后更新。这一点很容易，可以使用类似并查集路径压缩的方法实现，只需记录每个点向上遇到的第一条未被更新的边即可(因为有路径压缩，不一定要实时记录)。在每次更新时不断沿记录的指针向上走，直到走到或超越LCA(u,v)为止。Company Logo算法实现 算法3：求出最小生成树，对于每一条连接u,v的非树边排序，从小到大枚举非树边，利用类此于并查集的方法更新u到v的路径上所有树边。LCA的倍增求法：时间复杂度：O(MlogM+MlogN +Q)LCA的tarjan+并查集按秩合并的求法：时间复杂度：O(MlogM+M*a(N)+Q)空间复杂