题目分析与思路提示

1. 算法选择：Kruskal 算法

Kruskal 算法的核心思想是贪心 + 并查集。 它的逻辑非常符合直觉：既然要总成本最低，那我就优先修便宜的路！

2. 算法流程

1. 排序：将所有 $M$ 条备选道路按照成本 $w$ 从小到大排序。
2. 初始化：建立一个并查集，初始时 $N$ 个城市各自独立（$N$ 个集合）。
3. 遍历选边：
   • 依次拿出排序后成本最小的边 $(u, v)$。
   • 判断：利用并查集查询 $u$ 和 $v$ 是否已经连通（是否在同一个集合）。
     • 如果 find(u) != find(v)：说明这条路连接了两个原本不通的区域，必须修！
       • 累加成本到总结果。
       • 在并查集中合并 $u$ 和 $v$ (unite(u, v))。
       • 记录已修道路数 cnt++。
     • 如果 find(u) == find(v)：说明这两个城市之前已经通过其他（更便宜的）路连通了，这条路是多余的，跳过。
4. 终止条件：
   • 如果最终 cnt == N - 1，说明树已生成，输出总成本。
   • 否则，说明图不连通，输出 impossible。

3. 为什么不用 Dijkstra？

• Dijkstra 是求一个点到其他所有点的最短路径。
• MST 是求把所有点连在一起的最小总代价。
• 例子：三角形 ABC，边长 AB=5, BC=5, AC=6。
  • 从 A 出发 Dijkstra：到 B 是 5，到 C 是 6。路径总长没意义。
  • MST：选 AB(5) 和 BC(5)，总代价 10。AC(6) 太贵不选。

4. 复杂度分析

• 排序：$O(M \log M)$。
• 并查集操作：$M$ 次操作，每次接近 $O(1)$。
• 总复杂度：$O(M \log M)$。
• 对于 $2 \times 10^5$ 的数据，运算量约 $3 \times 10^6$，非常轻松。

参考代码 (C++14)

/**
 * 题目：大元的驿道 (The Postal Roads of Yuan)
 * 难度：GESP 6级
 * 算法：最小生成树 (Kruskal) = 排序 + 并查集
 */

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

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 并查集数组
int fa[MAXN];

// 初始化并查集
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}

// 查找根节点 (路径压缩)
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

// 合并集合
// 返回 true 表示合并成功（原本不在一个集合）
bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        fa[rootY] = rootX;
        return true;
    }
    return false;
}

// 定义边的结构体
struct Edge {
    int u, v, w;
};

// 比较函数，按权值从小到大排序
bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Edge> edges;
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    // 1. 贪心第一步：排序
    sort(edges.begin(), edges.end(), cmp);

    // 2. 初始化并查集
    init(N);

    long long total_cost = 0;
    int edges_count = 0;

    // 3. 遍历每一条边
    for (const auto& e : edges) {
        // 如果连接了两个不同的集合，则选中这条边
        if (unite(e.u, e.v)) {
            total_cost += e.w;
            edges_count++;
        }
    }

    // 4. 判断连通性
    // 生成树应该有 N-1 条边
    if (edges_count == N - 1) {
        cout << total_cost << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

生成策略：

• 为了保证图连通（对于有解的情况），我们先随机生成一棵树（保证骨架连通），然后再随机添加一些额外的边。
• 为了生成无解的情况，我们将点分成两个不连通的集合。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
struct Edge { int u, v, w; };
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }

struct DSU {
    vector<int> fa;
    DSU(int n) {
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) { fa[ry] = rx; return true; }
        return false;
    }
};

string solve(int N, int M, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), cmp);
    DSU dsu(N);
    long long cost = 0;
    int cnt = 0;
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            cost += e.w;
            cnt++;
        }
    }
    if (cnt == N - 1) return to_string(cost);
    else return "impossible";
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<Edge> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4; M = 5;
            edges = {{1,2,2}, {1,3,2}, {1,4,3}, {2,3,4}, {3,4,3}};
        }
        else if (i == 2) {
            // 样例2 (不连通)
            N = 3; M = 1;
            edges = {{1,2,5}};
        }
        else if (i <= 4) {
            // 小规模随机
            N = 20; M = 50;
            // 保证连通：先生成树
            for(int k=2; k<=N; k++) edges.push_back({randRange(1, k-1), k, randRange(1, 100)});
            // 再加随机边
            while(edges.size() < M) edges.push_back({randRange(1, N), randRange(1, N), randRange(1, 100)});
        }
        else if (i == 5) {
            // 刚好连通 (M=N-1, 是一棵树)
            N = 100; M = N-1;
            for(int k=2; k<=N; k++) edges.push_back({randRange(1, k-1), k, randRange(1, 100)});
        }
        else if (i == 6) {
            // 大规模不连通
            N = 1000; M = 2000;
            // 只连接 1~N/2，孤立 N/2+1~N
            for(int k=0; k<M; k++) edges.push_back({randRange(1, N/2), randRange(1, N/2), randRange(1, 100)});
        }
        else if (i == 7) {
            // 稠密图 (M 很大)
            N = 1000; M = 100000; // 接近 N^2/10
            for(int k=2; k<=N; k++) edges.push_back({randRange(1, k-1), k, randRange(1, 1000)});
            while(edges.size() < M) edges.push_back({randRange(1, N), randRange(1, N), randRange(1, 1000)});
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000; 
            if (i == 8) M = N - 1; // 树
            else if (i == 9) M = 200000; // 一般图
            else M = 200000; // Case 10

            // 保证连通的主干
            for(int k=2; k<=N; k++) edges.push_back({randRange(max(1, k-5), k-1), k, randRange(1, 10000)});
            // 随机边
            while(edges.size() < M) edges.push_back({randRange(1, N), randRange(1, N), randRange(1, 10000)});
        }

        // 写入输入
        fin << N << " " << edges.size() << "\n"; // M可能被调整
        for (const auto& e : edges) {
            fin << e.u << " " << e.v << " " << e.w << "\n";
        }

        // 写入输出
        fout << solve(N, (int)edges.size(), edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}