冬令营解题报告水管局长tube

1、IOI2006国家集训队作业：冬令营解题报告浙江 唐文斌水管局长解题报告浙江 唐文斌问题简述给定一个带权无向简单图 无重边，无自环G，要求在G 无重边，无自环删除一条已有的边(a,b)查询a、b两点之间最大边最小的路，返回这条最大边的权值规模：原图结点数N 1000边数M 100,000查询次数 Q 100,000其中保证删边操作不超过5000次。题目保证在任意时刻图G都连通算法分析本人在考试中没有做出此题，以下所说算法来源于讲题大会上朱晨光同学的发言。可以发现，本题最大的难点在于删边操作。因为删去一条边之后可能对整个图产生相当大的影响，这样我们就很难在一个比较短的时间内维护我们需要的信息。那

2、么，我们不妨把问题反过来看，先把图G中要删的边全删了，然后从最后一个命令开始倒着往上进行操作，那么“删边”操作就变成了相应的“加边”操作。这样的转化，在一定程度上简化了问题。现在，从简单情况入手，我们来考虑一下平常我们是如何求(a,b)两点之间最大边最小的路径的。首先，把所有的边按照权值从小到大进行排序，然后依次加入，直到a、b两点连通。而这个过程非常的类似于求最小生成树的Kruskal算法。所以，我们作如下猜想：猜想一 我们要维护一个图中任意两点间最大边最小的路径，只需要维护这个图的一棵最小生成树。这个猜想很显然是正确的，不失一般性，我们还是来证明一下：证明：设T是图G的一棵最小生成树。假设

3、猜想一错误，即存在一个点对(a,b)，点a到点b在T上的路径中最大边的权值为w；点a到点b在G中最大边最小的路径P上最大边权值为w0，满足w0 w。那么由假设可知在路径P上必然存在两个连续的点u、v，满足u、v在G中直接相连且满足边(u,v)的权值小于u、v两点在T中的路径上的最大边权值。那么我们只要用边(u,v)代替u、v两点在T中的路径上的最大边，就可以得到一棵更小的生成树，这与T是最小生成树矛盾，故猜想一成立。有了猜想一，我们现在所需要做的就是维护一棵最小生成树，完成以下两种操作：加一条新边，更新最小生成树查询两点(a,b)在生成树路径上的最大边权值下面提供两种实现的方法：算法一维护最小

4、生成树T。对于加边操作，设新边为(a,b)，在T中寻找a到b路径上的最大边e。若新边(a,b)权值大于e的权值，则用新边(a,b)代替e,更新最小生成树。这一步复杂度为。对于查询操作，直接在T中寻找a到b路径上的最大边e，返回e的权值。显然这一步操作是加边操作的一个子操作，复杂度也为。算法二我们现在要维护的是生成树中两个点之间路径上的最大边是多少，这很类似于一个经典问题RMQ问题。这里我们可以用类似的Sparse Table的方法来维护。对于当前的生成树T，我们随意选择一个节点为根，将无根树转化为有根树，并且维护两个表，和()，其实表示第i个节点往上走层的祖先。而表示从i到这一路径上的最大边权

5、值。显然这两个表都可以在时间内建立完成。对于加边操作，加边之后重构生成树，重新计算Ancestor和F数组，时间复杂度为。对于查询操作，我们需要查询(a,b)之间路径上的最大边权，设u等于a和b的最低公共祖先，那么我们的答案就是a到u路径上的最大边权与b到u路径上的最大边权得较大者。在Ancestor和F数组的帮助下，这一步可以在时间内完成，具体实现可参看附录中的程序。至此，问题已被解决，两个算法各有千秋，算法一在加边操作只需要线性的时间，但是查询也是线性的。而算法二虽然加边操作需要时间，但其查询操作却是的。小结在解决这道题目的过程中，我们把所有操作倒序处理，把“删边”操作对应为“加边”操作，这实际上是应用了“逆向思维”，这种思维方式帮助我们大大的简化了问题，为猜想一的出现提供了奠基，这是值得我们学习的。从冬令营考试中的规模来看，算法一与算法二已经足以对付