1231 最優(yōu)布線問(wèn)題

?

時(shí)間限制: 1 s 空間限制: 128000 KB 題目等級(jí) : 白銀 Silver 題目描述 Description

學(xué)校需要將n臺(tái)計(jì)算機(jī)連接起來(lái)，不同的2臺(tái)計(jì)算機(jī)之間的連接費(fèi)用可能是不同的。為了節(jié)省費(fèi)用，我們考慮采用間接數(shù)據(jù)傳輸結(jié)束，就是一臺(tái)計(jì)算機(jī)可以間接地通過(guò)其他計(jì)算機(jī)實(shí)現(xiàn)和另外一臺(tái)計(jì)算機(jī)連接。

為了使得任意兩臺(tái)計(jì)算機(jī)之間都是連通的（不管是直接還是間接的），需要在若干臺(tái)計(jì)算機(jī)之間用網(wǎng)線直接連接，現(xiàn)在想使得總的連接費(fèi)用最省，讓你編程計(jì)算這個(gè)最小的費(fèi)用。

輸入描述 Input Description

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

輸出描述 Output Description

輸出只有一行一個(gè)整數(shù)，表示最省的總連接費(fèi)用。

樣例輸入 Sample Input

3 3

1 2 1

1 3 2

2 3 1

樣例輸出 Sample Output

2

數(shù)據(jù)范圍及提示 Data Size & Hint

最終答案需要用long long類型來(lái)保存

?

水題 裸卡路絲卡爾

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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/6720130.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的1231 最优布线问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。