題目：

某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計(jì)表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達(dá)即可），并要求鋪設(shè)的公路總長度為最小。請(qǐng)計(jì)算最小的公路總長度。
Input
測(cè)試輸入包含若干測(cè)試用例。每個(gè)測(cè)試用例的第1行給出村莊數(shù)目N ( < 100 )；隨后的N(N-1)/2行對(duì)應(yīng)村莊間的距離，每行給出一對(duì)正整數(shù)，分別是兩個(gè)村莊的編號(hào)，以及此兩村莊間的距離。為簡單起見，村莊從1到N編號(hào)。
當(dāng)N為0時(shí)，輸入結(jié)束，該用例不被處理。
Output
對(duì)每個(gè)測(cè)試用例，在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
Huge input, scanf is recommended

分析與解答

kruskal算法：
按邊的權(quán)值的順序從小到大查一遍，如果不產(chǎn)生圈，（即是說u，v不在一個(gè)連通分量里），就把當(dāng)前這條邊（uv之間距離）加入生成樹中。

先看kruskal算法把，我那個(gè)sort第一次wa了，就是因?yàn)槲蚁聵?biāo)是從一開始的。

修修改改五分鐘寫了八道，我算是看出點(diǎn)門道，如果題目是以鄰接矩陣形式出現(xiàn)，就用prim算法，否則用kruskal算法。
而且這種題如果加額外條件，那無非就是改了一下標(biāo)記數(shù)組而已。。

#include<cstdio> #include<algorithm> using namespace std; int pre[10100 ]; int find(int x) //查找根節(jié)點(diǎn) { int r=x;while ( pre[r] != r ) //返回根節(jié)點(diǎn) rr=pre[r];int i=x , j ;while( i != r ) //路徑壓縮{j = pre[ i ]; //j是i的原來的父結(jié)點(diǎn) pre[ i ]= r ; //現(xiàn)在把i的父結(jié)點(diǎn)改成根節(jié)點(diǎn) i=j; //再把j的父節(jié)點(diǎn)改成根節(jié)點(diǎn) }return r ; } void join(int x,int y) //判斷x y是否連通，//如果已經(jīng)連通，就不用管了 如果不連通，就把它們所在的連通分支合并起, {int fx=find(x),fy=find(y);if(fx!=fy)pre[fx ]=fy; }struct node {int u,v,e; }; bool cmp(node a,node b){return a.e<b.e; } node edg[10010]; int m,sum; int k(){sort(edg+1,edg+m+1,cmp);for(int i=1;i<=m;++i) pre[i]=i;sum=0;for(int i=1;i<=m;++i){if(find(edg[i].u) != find(edg[i].v)){join(edg[i].u,edg[i].v);sum+=edg[i].e;} } return sum; } int main() {int t;while(scanf("%d",&t)){if(t==0) return 0;m=t*(t-1)/2;for(int i=1;i<=m;++i){scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].e);}printf("%d\n",k());} }

總結(jié)

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

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