By

问题描述

　　雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。
　　为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。
　　现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

　　输入的第一行包含两个正整数n, m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。
　　接下来m行，每行包含三个整数ai, bi, ci，表示第ai片麦田与第bi片麦田之间可以建立一条水渠，所需要的费用为ci。

输出格式

　　输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

样例输入

4 4
1 2 1
2 3 4
2 4 2
3 4 3

样例输出

6

样例说明

　　建立以下三条水渠：麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

评测用例规模与约定

　　前20%的评测用例满足：n≤5。
　　前40%的评测用例满足：n≤20。
　　前60%的评测用例满足：n≤100。
　　所有评测用例都满足：1≤n≤1000，1≤m≤100,000，1≤ci≤10,000。

题目解析

这是一道比较普通的最小生成树，利用Kruskal算法+并查集可以很快的解决这一道题。最小生成树的两个经典算法一个是Prim算法，另一个就是Kruskal算法了，Kruskal只要对边的权值进行排序，然后从小选择边，把边的两个顶点加入到集合中，这就要利用到并查集了。
并查集中每一个数据有一个代表元，也就是树根，而树根的代表元是自己。我们可以一直查找数据的father节点，直到查找到根节点，根节点的father是自己，这时候就找到了代表元，我们通过查找代表元是否相同，可以知道两个数据是否同属于一个集合。如果不是的话，使深度较小的那棵树的根节点的father等于另外一棵树的根节点，我们就完成了并查集的合并操作。剩下的就是在查找代表元的时候有一个可以使并查集查找效率更高的方法，就是路径压缩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<algorithm>
using namespace std;
struct WaterPath{
    short start;
    short end;
    short cost;
}waterPath[100100];

//定义集合
struct Set{
    short data;
    short rank;
    short parent;
}water[1001];

//初始化集合
void initSet(){
    for(int i=0;i<1001;i++){
        water[i].data=i;
        water[i].parent=i;
        water[i].rank=0;
    }
}

//查找集合代表元
int findparent(int s){
    if(water[s].parent!=water[s].data)
        water[s].parent=findparent(water[s].parent);//路径压缩
    return water[s].parent;
}

//合并集合
void union_set(int s1,int s2){
    int a=findparent(s1);
    int b=findparent(s2);
    if(water[a].rank>water[b].rank){
        water[b].parent=a;
    }
    else{
        water[a].parent=b;
        if(water[a].rank==water[b].rank){
            water[b].rank++;
        }
    }
}

//sort函数结构体排序的cmp函数
int cmp(const WaterPath &w1,const WaterPath &w2 ){
    return w1.cost<w2.cost;
}

int main(){
    initSet();
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        short start,end,cost;
        cin>>start>>end>>cost;
        waterPath[i].start=start;
        waterPath[i].end=end;
        waterPath[i].cost=cost;
    }
    sort(waterPath,waterPath+m,cmp);

    for(int i=0;i<m;i++){
        if(findparent(waterPath[i].start)!=findparent(waterPath[i].end)){
            sum+=waterPath[i].cost;
            union_set(waterPath[i].start,waterPath[i].end);
        }
    }
    cout<<sum<<endl;
    return 0;
}