题目链接

修复公路

题目描述

在一个国家中，有 个城市和 条双向公路。一场灾害后，所有公路都被损坏。

对于每条公路，我们知道它连接的两个城市以及修复它所需的时间。

你需要找出最早的时刻，使得任意两个城市之间都能够互相到达（直接或间接通过已修复的公路）。如果即使所有公路都修复完毕，图仍不连通，则输出 -1。

解题思路

这道题要求我们找到一个最小的时间，使得所有城市构成一个连通图。问题的核心在于，如果我们能在时间 达成目标，那么在任何大于 的时间点，目标也一定是达成的。这暗示了我们可以通过某种方式寻找这个关键的“瓶颈”时间点。

这正是**最小生成树（Minimum Spanning Tree, MST）**算法的应用场景，特别是 Kruskal 算法。Kruskal 算法的思想与本题的需求完美契合。

算法步骤如下：

  1. 抽象模型：

    • 将 个城市看作图的 个顶点。
    • 将 条公路看作图的 条边。
    • 将每条公路的修复时间看作对应边的权重。

  2. 排序：

    将所有 条公路（边）按照它们的修复时间（权重）从小到大进行排序。这代表了我们修复公路的顺序：总是优先修复耗时最短的。

  3. 使用并查集 (DSU) 连接城市：

    我们使用并查集数据结构来维护城市的连通状态。初始时，每个城市自成一个连通分量。

  4. 遍历与合并：

    我们按排好序的顺序，依次遍历每一条公路 ，其修复时间为 ：

    • 使用并查集的 find 操作检查城市 和城市 是否已经连通。
    • 如果它们尚未连通：说明修复这条公路是必要的，因为它连接了两个不同的城市群。我们执行 unite 操作合并它们所在的集合，并将已连接的边数（或已合并的组件数）加一。此时，最新的“最晚修复时间”就是当前公路的修复时间 。
    • 如果它们已经连通：修复这条公路对于实现全局连通没有新的贡献（会形成环），因此跳过。

  5. 确定最终时间：

    当且仅当我们成功连接了 条有效的公路时，所有 个城市才首次构成一个单一的连通分量。在这个过程中，我们所加入的第 条公路的修复时间，就是使得全图连通所需要的“最晚”的一条路的时间，因此也就是我们要求的“最早”的全局通车时间。

  6. 处理无法连通的情况：

    如果在遍历完所有 条公路后，我们添加的有效公路数量仍少于 ，这意味着即使所有路都修完，原图的某些部分也是孤立的，无法形成一个完整的连通图。此时，应输出 -1。

综上所述，该问题的解就是构造该图的最小生成树过程中，最后一条被加入的边的权重。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

struct Road {
    int u, v, time;
};

bool compareRoads(const Road& a, const Road& b) {
    return a.time < b.time;
}

vector<int> parent;

int find_root(int i) {
    if (parent[i] == i) {
        return i;
    }
    return parent[i] = find_root(parent[i]);
}

bool unite_sets(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_b] = root_a;
        return true;
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<Road> roads(m);
    for (int i = 0; i < m; ++i) {
        cin >> roads[i].u >> roads[i].v >> roads[i].time;
    }

    sort(roads.begin(), roads.end(), compareRoads);

    parent.resize(n + 1);
    iota(parent.begin(), parent.end(), 0);

    int edges_count = 0;
    int max_time = 0;

    for (const auto& road : roads) {
        if (unite_sets(road.u, road.v)) {
            edges_count++;
            max_time = road.time;
            if (edges_count == n - 1) {
                break;
            }
        }
    }

    if (edges_count == n - 1) {
        cout << max_time << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Road implements Comparable<Road> {
    int u, v, time;

    public Road(int u, int v, int time) {
        this.u = u;
        this.v = v;
        this.time = time;
    }

    @Override
    public int compareTo(Road other) {
        return Integer.compare(this.time, other.time);
    }
}

public class Main {
    private static int[] parent;

    public static int findRoot(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = findRoot(parent[i]);
    }

    public static boolean uniteSets(int a, int b) {
        int rootA = findRoot(a);
        int rootB = findRoot(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Road> roads = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            roads.add(new Road(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(roads);

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int edgesCount = 0;
        int maxTime = 0;

        for (Road road : roads) {
            if (uniteSets(road.u, road.v)) {
                edgesCount++;
                maxTime = road.time;
                if (edgesCount == n - 1) {
                    break;
                }
            }
        }

        if (edgesCount == n - 1) {
            System.out.println(maxTime);
        } else {
            System.out.println(-1);
        }
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(200005)

def find_root(i):
    if parent[i] == i:
        return i
    parent[i] = find_root(parent[i])
    return parent[i]

def unite_sets(a, b):
    root_a = find_root(a)
    root_b = find_root(b)
    if root_a != root_b:
        parent[root_b] = root_a
        return True
    return False

def main():
    n, m = map(int, sys.stdin.readline().split())
    
    roads = []
    for _ in range(m):
        u, v, t = map(int, sys.stdin.readline().split())
        roads.append((u, v, t))

    # 按修复时间排序
    roads.sort(key=lambda x: x[2])

    global parent
    parent = list(range(n + 1))

    edges_count = 0
    max_time = 0

    for u, v, time in roads:
        if unite_sets(u, v):
            edges_count += 1
            max_time = time
            if edges_count == n - 1:
                break
    
    if edges_count == n - 1:
        print(max_time)
    else:
        print(-1)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Kruskal 算法（基于排序和并查集）
  • 时间复杂度：。瓶颈在于对 条公路进行排序。之后遍历公路并执行并查集操作的时间为 ，其中 是反阿克曼函数，通常可视为常数。因此，总时间由排序主导。
  • 空间复杂度：，需要 空间存储并查集， 空间存储所有公路信息。