题目

点击显/隐题目

随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。
所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。

每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行，每行描述一条路线，其中第i行为3个整数N1i, N2i, V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1i, N2i<=N, N1i≠N2i, 1<=V_i<=10^3.
对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。

对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。

5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185

题解

模板题

代码

点击显/隐代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;

int f[maxn];
struct Edge {
    int u, v;
    int w;
    bool operator<(const Edge rhs) const { return w < rhs.w; }
} e[maxm];
int pos;

int ufs(int x) { return f[x] == x ? x : f[x] = ufs(f[x]); }
int Kruskal(int n, int m) {
    int w = 0;
    for (int i = 0; i <= n; i++)
        f[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; i++) {
        int x = ufs(e[i].u), y = ufs(e[i].v);
        if (x != y) {
            f[x] = y;
            w += e[i].w;
        }
    }
    return w;
}
void addEdge(int u, int v, int w) {
    e[pos].u = u;
    e[pos].v = v;
    e[pos].w = w;
    pos++;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        int u, v, w;
        pos = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
        }
        printf("%d\n", Kruskal(n, m));
    }
}

OhYee