題目鏈接
現(xiàn)有村落間道路的統(tǒng)計(jì)數(shù)據(jù)表中，列出了有可能建設(shè)成標(biāo)準(zhǔn)公路的若干條道路的成本，求使每個(gè)村落都有公路連通所需要的最低成本。

輸入格式:

輸入數(shù)據(jù)包括城鎮(zhèn)數(shù)目正整數(shù)N（≤1000）和候選道路數(shù)目M（≤3N）；隨后的M行對(duì)應(yīng)M條道路，每行給出3個(gè)正整數(shù)，分別是該條道路直接連通的兩個(gè)城鎮(zhèn)的編號(hào)以及該道路改建的預(yù)算成本。為簡(jiǎn)單起見(jiàn)，城鎮(zhèn)從1到N編號(hào)。

輸出格式:

輸出村村通需要的最低成本。如果輸入數(shù)據(jù)不足以保證暢通，則輸出?1，表示需要建設(shè)更多公路。

輸入樣例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
輸出樣例:

12

#include<iostream> #include<algorithm> using namespace std; int f[1001]; typedef struct Node{int aa;int bb;int fei; }Node; bool cmp(Node a,Node b){return a.fei < b.fei; } int getf(int x){if(f[x] == x)return f[x];f[x] = getf(f[x]);return f[x]; } int merge(int x,int y){int tx = getf(x);int ty = getf(y);if(tx != ty){f[ty] = tx;return 1;}return 0; } void init(int n){for(int i = 1;i <= n;i++)f[i] = i;return; } int main(){int n,m,a,b,fee,sum,cnt;Node p[3001];//設(shè)置為3001,一開(kāi)始設(shè)置成了1001,后來(lái)發(fā)現(xiàn)題目中候選道路數(shù)目M≤3N,與m看齊 scanf("%d%d",&n,&m);init(n);//并查集初始化 for(int i = 0;i < m;i++){scanf("%d%d%d",&a,&b,&fee);p[i].aa = a;p[i].bb = b;p[i].fei = fee;} sort(p,p + m,cmp); //按照權(quán)值的大小進(jìn)行排序 sum = 0,cnt = 0;for(int i = 0;i < m;i++)//最小生成樹(shù),循環(huán)n-1次,結(jié)點(diǎn)的個(gè)數(shù)減一 if(merge(p[i].aa,p[i].bb)){sum += p[i].fei;cnt++;//統(tǒng)計(jì)邊數(shù) }if(cnt == n- 1)printf("%d\n",sum);elseprintf("-1\n"); return 0; }

總結(jié)

以上是生活随笔為你收集整理的7-9 公路村村通（30 分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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