洛谷P1111题解：修复公路问题的最优解法

一、问题描述

给定N个村庄和M条公路，每条公路连接两个村庄并有修复时间t。求最早什么时候所有村庄可以连通，如果不能连通则输出-1。

二、算法核心思想

本解决方案采用并查集数据结构结合Kruskal算法：

1. 使用并查集管理村庄连通性

2. 按修复时间排序所有公路

3. 依次选择最短修复时间的公路进行连接

4. 当所有村庄连通时输出最大修复时间

三、完整代码实现（带详细注释）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 定义公路结构体
struct Edge {
    int u, v, t;  // u和v表示连接的村庄，t表示修复时间
    bool operator<(const Edge& other) const {
        return t < other.t;  // 按修复时间排序
    }
};

vector<int> parent;  // 并查集父节点数组

// 查找根节点（带路径压缩）
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

// 合并两个集合
bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return false;  // 已经在同一集合
    parent[y] = x;  // 合并
    return true;
}

int main() {
    int N, M;  // N个村庄，M条公路
    cin >> N >> M;
    vector<Edge> edges(M);  // 存储所有公路
    parent.resize(N+1);  // 初始化并查集
    
    // 初始化每个村庄的父节点为自己
    for(int i=1; i<=N; i++) parent[i] = i;
    
    // 输入公路信息
    for(int i=0; i<M; i++) 
        cin >> edges[i].u >> edges[i].v >> edges[i].t;
    
    // 按修复时间排序
    sort(edges.begin(), edges.end());
    
    int cnt = 0, max_t = 0;  // cnt记录已连接边数，max_t记录最大时间
    for(auto& e : edges) {
        if(unite(e.u, e.v)) {  // 如果成功连接
            max_t = max(max_t, e.t);  // 更新最大时间
            if(++cnt == N-1) break;  // 已连接N-1条边，所有村庄连通
        }
    }
    
    // 输出结果：如果连通输出最大时间，否则输出-1
    cout << (cnt == N-1 ? max_t : -1) << endl;
    return 0;
}

四、算法分步解析

1. 数据结构准备：

• 定义Edge结构体存储公路信息

• 实现并查集的find和unite操作

• 初始化并查集数组

2. 输入处理阶段：

• 读取村庄数量和公路数量

• 存储所有公路信息

• 按修复时间排序公路

3. 核心算法阶段：

• 依次处理每条公路

• 使用并查集判断是否连接新村庄

• 更新最大修复时间

• 检查是否所有村庄已连通

4. 结果输出：

• 根据连通情况输出结果

五、常见误区与调试技巧

1. 忘记初始化并查集数组

2. 路径压缩实现错误

3. 排序标准设置错误

4. 连通性判断条件错误

六、扩展思考

1. 如何优化空间复杂度？

2. 如果要求输出具体修复方案该如何修改？

3. 如何可视化这个连接过程？

4. 如果村庄之间有距离限制该如何处理？