Problem Description
某省調(diào)查鄉(xiāng)村交通狀況，得到的統(tǒng)計(jì)表中列出了任意兩村莊間的距離。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)村莊間都可以實(shí)現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過(guò)公路可達(dá)即可），并要求鋪設(shè)的公路總長(zhǎng)度為最小。請(qǐng)計(jì)算最小的公路總長(zhǎng)度。
Input
測(cè)試輸入包含若干測(cè)試用例。每個(gè)測(cè)試用例的第1行給出村莊數(shù)目N ( < 100 )；隨后的N(N-1)/2行對(duì)應(yīng)村莊間的距離，每行給出一對(duì)正整數(shù)，分別是兩個(gè)村莊的編號(hào)，以及此兩村莊間的距離。為簡(jiǎn)單起見(jiàn)，村莊從1到N編號(hào)。
當(dāng)N為0時(shí)，輸入結(jié)束，該用例不被處理。
Output
對(duì)每個(gè)測(cè)試用例，在1行里輸出最小的公路總長(zhǎng)度。
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
代碼
#include<stdio.h>
#include<string.h>
#define MAX 1000000
#define M 225
int know[M];
int min[225];
int path[M][M]=
{0};
int p;
int prim()
{
int ret=0;
int i,j,k;
for(i=1;i<=p;i++)
{
min[i]=66535000;
know[i]=0;
}
min[1]=0;
for(i=1;i<=p;i++)
{
k=-1;
for(j=1;j<=p;j++)
{
if(!know[j]&&(k==-1||min[j]<min[k]))
k=j;
}
know[k]=1;
ret+=min[k];555
for(j=1;j<=p;j++)
if(!know[j]&&path[k][j]&&path[k][j]<min[j])
min[j]=path[k][j];
}
return ret;
}
int main()
{
int n;int i;
int r,a,b,c;
while(scanf("%d",&p)!=EOF&&p!=0)
{
r=p*(p-1)/2;
memset(path,0,sizeof(path));
for(i=0;i<r;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(!path[a][b]||path[a][b]>c)
path[a][b]=c;
}
printf("%d\n",prim());
}
return 0;
}
posted on 2012-07-19 21:01
天YU地___PS，代碼人生 閱讀(190)
評(píng)論(0) 編輯 收藏