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

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

輸出格式:
輸出村村通需要的最低成本。如果輸入數(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 <bits/stdc++.h> #define MAXSIZE 1001 using namespace std; int bcj[1001]; struct rur {int x;int y;int wei; }r[3*MAXSIZE]; typedef struct rur Made; bool cmp(Made F,Made E) {return F.wei<E.wei; } int Found(int a); int main() {int n,m,sum=0; //sum記錄花費 cin>>n>>m;for (int i=1;i<=n;i++) //構(gòu)造群集合（并查集）{bcj[i]=i;}int a,b,wei;for (int i=0;i<m;i++){cin>>a>>b>>wei;r[i].x=a;r[i].y=b;r[i].wei=wei;}sort(r,r+m,cmp); //排序int now=0; //已經(jīng)添加的邊數(shù) for (int i=0;i<m;i++) //由小到大 {int Bossx,Bossy;Bossx=Found(r[i].x);Bossy=Found(r[i].y);if (Bossx==Bossy){continue;}sum+=r[i].wei;now++;if (now==n-1){break;}bcj[Bossx]=Bossy;}if (now<n-1) //輸入的數(shù)據(jù)不足 {printf("-1\n"); //printf("**%d**\n",now);return 0;}printf("%d",sum);return 0; }int Found(int a) //找a的老大是誰 {if (a==bcj[a]) return a;else{return Found(bcj[a]); //無壓縮 } } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

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

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