公路通

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef struct
 4 {
 5     int a,b;
 6     int price=99999;
 7 }lu;
 8 bool cmp(lu a,lu b)
 9 {
10     return a.price<b.price;
11 }
12 lu a[3001];
13 int   p[1001];
14 int main()
15 {
16     int n,m;
17     int fei=0;
18     int num=0;//记录加入的边数
19     scanf("%d%d",&n,&m);
20     for(int i=1;i<=m;i++)
21     {
22         cin>>a[i].a>>a[i].b>>a[i].price;
23     }
24     for(int i=1;i<=n;i++)
25     {
26         p[i]=i;//每个点先赋值一个初始集合
27     }
28     sort(a+1,a+m,cmp);
29     for(int i=1;i<=m;i++)
30     {
31         if(p[a[i].a]!=p[a[i].b])//这条边的两个端点还不属于一个集合
32         {
33             num++;//已经加入的边数++
34             fei+=a[i].price;//价钱++
35             int z=p[a[i].b];
36             for(int j=1;j<=n;j++)
37             {
38                 if(p[j]==z)
39                 {
40                     p[j]=p[a[i].a];//找出之前已经同化的所有顶点并且让他重新同化
41                 }
42             }
43             if(num==n-1)
44                 break;
45         }
46     }
47     if(num==n-1)
48         cout<<fei;
49     else if(num<n-1)
50     {
51         cout<<"-1";
52     }
53 }