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

解題思路：

典型的最小生成樹的問題，利用krusal算法代碼簡潔效率高。

但是在構建圖的時候盡量不要用鄰接矩陣，因為鄰接矩陣既浪費空間有耗時間，采用鄰接表更好

正解：

#include<cstdio> #include<algorithm> typedef struct {int from;int to;int value; }Node,*node; int Find(int *father,int x) {if(x!=father[x])father[x]=Find(father,father[x]);return father[x]; } void Union(int *father,int from,int to) {int a=Find(father,from);int b=Find(father,to);father[a]=b; } bool cmp(const Node & a,const Node & b) {return a.value<b.value;//從小到大排序 } using namespace std; int main() {int N,i=0;while(~scanf("%d",&N),N){Node mp[N*N+1];int father[N+1];for(i=0;i<=N;i++)father[i]=i;for(i=0;i<N*(N-1)/2 ;i++)scanf("%d%d%d",&mp[i].from,&mp[i].to,&mp[i].value);sort(mp,mp+N*(N-1)/2,cmp);int sum=0;for(i=0;i<N*(N-1)/2;i++){if(Find(father,mp[i].from)!=Find(father,mp[i].to)){Union(father,mp[i].from,mp[i].to);sum+=mp[i].value;}//printf("%d %d %d\n",mp[i].from,mp[i].to,mp[i].value);}printf("%d\n",sum);}return 0; } 開始寫時的錯誤代碼：

因為”動態“數組的邊界數開的范圍不正確

#include<algorithm>//Runtime Error(ACCESS_VIOLATION)
#include<cstdio>
int Find(int * helper,int a)//傳遞了數組的地址?
{
if(a!=helper[a])
helper[a]=Find(helper,helper[a]);
return helper[a];
}//并查集FIND?
void Union(int * helper,int a,int b)//傳遞了數組的地址?
{
int x=Find(helper,a);//找a的父節點?
int y=Find(helper,b);//b的父節點?
helper[y]=x;//合并?
}//并查集UNION?
typedef struct M
{
int a;
int b;
int v;
}Node;//存儲圖的邊(u,v)以及對應的值?
bool cmp(const Node & x,const Node & y)
{
return x.v<y.v;
}//sort排序，對值進行降序排序?
using namespace std;
int main(void)
{
int N;
while(scanf("%d",&N)!=EOF&&N)
{
Node vex[N];//存儲(u,v)關系(錯誤）?
int helper[N+1];//新建并查集?
for(int i=0;i<N+1;i++)
helper[i]=i;//并查集初始化?
int T=0;
while(T!=N*(N-1)/2)
scanf("%d%d%d",&vex[T].a,&vex[T].b,&vex[T++].v);
sort(vex,vex+N,cmp);
int sum=0;
for(int i=0;i<N;i++)//K...算法?
{
if(Find(helper,vex[i].a)!=Find(helper,vex[i].b))
{
Union(helper,vex[i].a,vex[i].b);
sum+=vex[i].v;//記錄樹的總值?
}?
}
printf("%d\n",sum);
}
return 0;
}

總結

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

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