Problem Description

某省調查鄉村交通狀況，得到的統計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。請計算最小的公路總長度。

Input

測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數目N ( < 100 )；隨后的N(N-1)/2行對應村莊間的距離，每行給出一對正整數，分別是兩個村莊的編號，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號。

當N為0時，輸入結束，該用例不被處理。

Output

對每個測試用例，在1行里輸出最小的公路總長度。

Sample Input

3

1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output

3

5

思路：最小生成樹Prim算法經典例題，套用模版即可。

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<string> #define INF 999999999 #define N 101 #define MOD 1000000007 #define E 1e-12 using namespace std; int g[N][N]; bool vis[N]; int minn[N]; int main() {int n;while(scanf("%d",&n)!=EOF&&n){int edge=n*(n-1)/2;for(int i=1;i<=edge;i++){int x,y,dis;scanf("%d%d%d",&x,&y,&dis);g[x][y]=dis;g[y][x]=dis;}memset(minn,0x7f,sizeof(minn));memset(vis,0,sizeof(vis));minn[1]=0;for(int i=1;i<=n;i++){int k=0;for(int j=1;j<=n;j++)//尋找與白點相連的權值最小的藍點kif(vis[j]==0&&minn[j]<minn[k])k=j;vis[k]=1;//藍點k加入生成樹，標記為白點for(int j=1;j<=n;j++)//修改所有與k相連的藍點if(vis[j]==0&&g[k][j]<minn[j])minn[j]=g[k][j];}int MST=0;for(int i=1;i<=n;i++)//計算權值和MST+=minn[i];cout<<MST<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的还是畅通工程（HDU-1233）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。