posts - 36, comments - 3, trackbacks - 0

Problem Description

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

Input

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

Output

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

Sample Input

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;
}