【codevs1231】最优布线问题

problem

solution

codes

//MST-Kruskal-排序贪心+并查集
//题中N=M,(M小于N^2的)稀疏图用邻接表。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100010;

struct Edge{ int u, v, w; }e[maxn];
bool cmp(Edge a, Edge b){return a.w<b.w;}

int fa[maxn];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    LL ans = 0;
    init(n);
    for(int i = 1; i <= m; i++){
        int u = e[i].u, v = e[i].v;
        if(find(u) != find(v)){
            merge(u,v);
            ans += e[i].w;
        }
    }
    cout<<ans<<"\n";
    return 0;
}
  

 

  
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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80543093