基础图论_Kruskal算法

P1111 修复公路

题目背景

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出 A 地区的村庄数 $N$，和公路数 $M$，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。

输入格式

第 $1$ 行两个正整数 $N,M$。

下面 $M$ 行，每行 $3$ 个正整数 $x,y,t$，告诉你这条公路连着 $x,y$ 两个村庄，在时间 $t$ 时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 $-1$，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例 #1

输入 #1

4 4
1 2 6
1 3 4
1 4 5
4 2 3

输出 #1

5

说明/提示

$1\leq x, y\leq N \le 10 ^ 3$，$1\leq M, t \le 10 ^ 5$。

解决方案

这道题目要求我们寻找一个关键路径，即将所有的村庄连接起来之后耗时最长的一条权边的值为多少。那么我们就可以使用Kruskal算法或者Prim算法在村庄之间生成一条最小生成树。

而Kruskal算法和Prim算法在最终的实现效果上并无太大区别，只是实现方式有所不同，而Kruskal算法中采用了我们已经熟悉的并查集算法，为了节约备赛时间，我们在这里先只研究Kruskal算法在上述题目场景中的实现。

Kruskal算法的基本思想在图中不断寻找两点之间最小的权边，如果这两点尚未连接，就将该权边添加到最终结果之中，否则就跳过，知道生成一个最小生成树为止。那么如果不使用二维数组进行更新的话，并查集在这里就有很好的适用性，我们可以使用union函数将拥有最小权边的两点连接起来，并在随后使用find函数找到根节点，中间可以使用一个time数组来记录关键权值。

以下是Python中上述思路的具体实现。

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size+1))
        self.time = [0] * (size+1)

    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    def union(self, x, y):
        xx, yy = self.find(x), self.find(y)
        if xx == yy:
            return
        self.pa[yy] = xx
        self.time[xx] = max(self.time[xx], self.time[yy])

def main():
    n, m = map(int, input().split())

    routes = []
    for i in range(m):
        x, y, t = map(int, input().split())
        routes.append((x, y, t))

    # 使用匿名函数对原数据排序
    village = Dsu(n)
    routes.sort(key=lambda x: x[2])

    # 依次连接尚未在同一棵树上的两个新结点
    for x, y, t in routes:
        if village.find(x) != village.find(y):
            village.time[x] = t if village.time[x] == 0 else max(village.time[x], t)
            village.time[y] = t if village.time[y] == 0 else max(village.time[y], t)
            village.union(x, y)

    # 开始判断森林中是否只有一个根结点
    # 如果不是，说明有村庄没有被联通
    fathers = []
    for i in range(1, n+1):
        if village.pa[i] == i:
            fathers.append(village.time[i])

    if len(fathers) != 1:
        print(-1)
    else:
        print(fathers[0])

if __name__ == "__main__":
    main()

Bingo!