学步园

  题意：给你几种型号的truck （每种都不一样） 每两种型号的距离为他们对应的字符不同的个数
要求所有型号间的最短距离。（即将所有型号用一条线连起来，线最短）
  思路：简单的prim

#include <stdio.h>
#include <string.h>
#define M 2005
char str[M][10];
int dis[M][M];
int dif(char s1[],char
s2[])   
//两串的距离
{
    int
i,j,count;
    count =
0;
    for (i = 0;i
< 7;i ++)
       
if (s1[i] != s2[i])
           
count ++;
    return
count;
}

void prim (int n)
{
    int
cost[M],flag[M];
    int
i,j,k,sum,min;
    for (i = 0;i
< n;i ++)
    {
       
cost[i] = dis[0][i];
       
flag[i] = 0;
    }
    flag[0] =
1;
    sum =
0;
    for (i = 1;i
< n;i ++)
    {
       
min = 10;
       
for (j = 1;j < n;j ++)
       
{
           
if (flag[j] == 0&&cost[j]
< min)
           
{
               
min = cost[j];
               
k = j;
           
}
       
}
       
flag[k] = 1;
       
sum += cost[k];
       
for (j = 1;j < n;j ++)
           
if (cost[j] > dis[k][j])
               
cost[j] = dis[k][j];
    }
    printf ("The
highest possible quality is 1/%d.\n",sum);
}
int main ()
{
    int
n,i,j,count;
    while (scanf
("%d",&n)&&n)
    {
       
getchar ();
       
for (i = 0;i < n;i ++)