Data Structure 2012

这道题目有很多种做法，下面我说一下我的做法：

这道题目的本质就是求一个会聚点，使得两个分身到达本体的时间和最小。

由于本体不会移动，所以只需要枚举三次即可。

剩下的问题就是如何求分身到达本体的时间了，这个是一个单源最短路模型。

其实可以直接用BFS暴力过掉，暴力过掉当然还需要一些技巧，我用的就是SPFA。

至于什么是SPFA，请看：SPFA reference

当然，这道题的主人佘召臣有一个巧妙的构图方法，大家可以找他问一下。

这是作业题中的翻版，首先说一下这道题的数据容易引起误解。

比如A和B是Group1和Group2的强者，每次询问后不是输出max(A/2,B/2)，而是输出Group1和Group2并成一堆后，最强者。

然后就是怎么做这道题目了，熟读了题目之后发现这道题目涉及合并操作，以及找最大值操作。

对于合并操作，我们能想到并查集，就是每次合并，将一堆人的首领和另一堆人的首领合并。

下面就是找最大值的问题了，考场上有不少同学没思考清楚，直接在并查集的基础上做了一些不科学的改动，拿不到满分。

其实想一想，找最大值用堆维护不就行了嘛。

总结一下思路，这道题可以用并查集加上堆来解决，具体地说就是每一个集合里面建一个大根堆。

初始时有N个堆，每个堆只有一个元素。

每次合并，就将一堆删去，并入另外一堆。

这样的确很暴力，不过至少可以通过7个点，已经很不错了。

当然，由于作业里面出现了左堆，那么可以直接将堆换成左堆，大大减少了合并时间，数据就全过了。

这道题目就是N路合并问题，如果不知道什么是N路合并，可以考虑N=2的情形。

两个有序队列做合并，数据结构课里面应该讲过怎么做吧。现在我们将N扩大，然后就是N个有序队列做合并。