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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int N=1e5+10;
 
int n,m;
struct node{
    int a,b,w;
    bool operator< (const node& W)const    //每条边按权重排序 
    {
        return w<W.w;
    }
}nod[N];
int p[N];
int find(int x)    //并查集模版 
{
    if(p[x]==x)
    return x;
    p[x]=find(p[x]);
    return p[x];
}
 
 
 
int main(void)
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        nod[i]={a,b,w};
    }
    sort(nod,nod+m);
    for(int i=1;i<=n;i++)
    p[i]=i;
     
    int res=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=nod[i].a;
        int b=nod[i].b;
        int w=nod[i].w;
        a=find(a),b=find(b);
        if(a!=b)        //如果a集合和b集合没连上,就连上,边数++; 
        {
            res+=w;
            cnt++;
            p[a]=b;
        }
    }
    if(cnt<n-1)    //n个点至少需要n-1个边 ,小于就是无法构成最短生成树 
    puts("impossible");
    else
    cout<<res<<endl;
    return 0;
}


点赞(0)
 

0 分

0 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论