1231 最優佈線問題

1231 最優佈線問題

學校需要將n台電腦連接起來，不同的2台電腦之間的連接費用可能是不同的。為了節省費用，我們考慮採用間接數據傳輸結束，就是一臺電腦可以間接地通過其他電腦實現和另外一臺電腦連接。

為了使得任意兩台電腦之間都是連通的（不管是直接還是間接的），需要在若幹台電腦之間用網線直接連接，現在想使得總的連接費用最省，讓你編程計算這個最小的費用。

輸入第一行為兩個整數n,m（2<=n<=100000，2<=m<=100000），表示電腦總數，和可以互相建立連接的連接個數。接下來m行，每行三個整數a,b,c 表示在機器a和機器b之間建立連接的話費是c。(題目保證一定存在可行的連通方案, 數據中可能存在權值不一樣的重邊，但是保證沒有自環)

輸出只有一行一個整數，表示最省的總連接費用。

3 3

1 2 1

1 3 2

2 3 1

2

最終答案需要用long long類型來保存

水題 裸卡路絲卡爾

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=300001;
 7 struct node
 8 {
 9     int u;
10     int v;
11     int w;
12 }edge[MAXN];
13 int num=1;
14 int father[MAXN];
15 int comp(const node & a,const node & b)
16 {
17     if(a.w<b.w)return 1;
18     else return 0;
19 }
20 int find(int x)
21 {
22     if(father[x]!=x)
23     father[x]=find(father[x]);
24     return father[x];
25 }
26 void unionn(int x,int y)
27 {
28     int fx=find(x);
29     int fy=find(y);
30     father[fx]=fy;
31 }
32 int main()
33 {
34     int n,m;
35     scanf("%d%d",&n,&m);
36     for(int i=1;i<=n;i++)father[i]=i;
37     for(int i=1;i<=m;i++)
38     {
39         scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w);
40         num++;
41     }
42     sort(edge+1,edge+num,comp);
43     long long int k=0;
44     long long int tot=0;
45     for(int i=1;i<=num-1;i++)
46     {
47         if(find(edge[i].u)!=find(edge[i].v))
48         {
49             unionn(edge[i].u,edge[i].v);
50             tot=tot+edge[i].w;
51             k++;
52         }
53         if(k==n-1)break;
54     }
55     printf("%lld",tot);
56     return 0;
57 }