poj1789 Truck History （最小生成樹）

歷史上，曾用7個小寫字母來表示每種truck的型號，每兩種型號之間的差距為字母串中不同字母的個數。現在給出n種不同型號的truck，問怎樣使 1/Σ(to,td)d(to,td)的值最小。（即找到一條連接所有truck的最短路徑。典型的最小生成樹的問題， discuss裡說，Prim算法適合稠密圖，Kruskal算法適合稀疏圖，可以使用prim和kruskal兩種方法。該題是稠密的圖。求最小生成樹的最段路徑問題：
[csharp] 
#include"stdio.h" 
#include"string.h" 
#define INF 1000000000 
int mark[2001],f[2001],n; 
char str[2001][8]; 
int fun(int i,int j)//每兩種型號之間的distant為字符串中不同字母的個數！ 
{ 
    int t,k; 
    t=0; 
    for(k=0;k<7;k++) 
    { 
        if(str[i][k]!=str[j][k]) 
            t++; 
    } 
    return t; 
} 
void prime() 
{ 
    int i,j,min,k,ans; 
    memset(mark,0,sizeof(mark)); 
    for(i=0;i<n;i++) 
        f[i]=fun(0,i); 
    f[0]=0;mark[0]=1; 
    ans=0; 
    for(i=0;i<n-1;i++) 
    { 
        min=INF; 
        for(j=0;j<n;j++) 
        { 
            if(!mark[j]&&min>f[j]) 
            { 
                min=f[j];k=j; 
            } 
        } 
        ans+=min; 
        mark[k]=1; 
        for(j=0;j<n;j++) 
        { 
            if(!mark[j]&&f[j]>fun(k,j)) 
                f[j]=fun(k,j); 
        } 
    } 
    printf("The highest possible quality is 1/%d.\n",ans); 
} 
int main() 
{ 
    int i,j; 
    while(scanf("%d",&n)!=-1) 
    { 
        if(n==0)break; 
        for(i=0;i<n;i++) 
            scanf("%s",str[i]); 
        prime(); 
    } 
    return 0; 
} 

作者：yyf573462811