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

补充：软件开发 , C# ,