[POJ]1679 The Unique MST

这道题要我们求最小生成树是不是唯一的，其实就是让我们求次小生成树，如果次小生成树和最小生成树的权值是一样的，说明最小生成树不唯一；反之说明唯一。
那么问题就转化为如何求次小生成树，首先我们可以用Prim或者Kruskal求得MST。那么对于其余所有不在MST里的边，我们可以枚举每次插入MST，那么MST一定以形成一个环。我们删除环上除了新插入边之外权值最大的边，那么新得到的生成树T就是包含被插入边的MST，但是显然这个时间复杂度太高了。如果对于新插入的边(u, v)，我们有更快的办法找到新形成的环上的除去新加入的边之外的最长边的话，就可以大大优化时间复杂度。Prim和Kruskal在这里就有一个非常好的应用：

• Kruskal算法中，我们每次取边e连接S和S'两个顶点集合的时候，e就是所有S中的节点u到S'中节点v路径上的最长边。证明显而易见，因为kruskal是按照边权值从小到大加的。
• Prim算法中，我们每次取连接顶点集S和V-S的边e(u, v)的时候，假设u是在S当中的节点，对于任意在S当中的节点i，其到v的路径上最长的边maxCost[i][v] = max(maxCost[i][u], e.cost)，我们只要一直维护maxCost矩阵就行。

所以我们在建立MST的时候就可以求得MST中任意两点(u, v)路径上最长的边，之后我们只需要枚举所有不在MST上的点来求次小生成树即可。建立MST的时间复杂度是O(E * log E)，求任意两点路径上的最长边时间复杂度O(V^2)，枚举每一条边的时间复杂度也是O(V^2)，所以总的时间复杂度是O(V^2 + E * log E)。代码如下：

Prim的做法:

Kruskal的做法: