学步园

#include <stdio.h>
#include <iostream>
using namespace std;
int n,dist[2002][2002];
char ch[2002][7];
int sum;

int distance(char a[],char b[]){
  int dc=0;
  for(int i=0;i<7;i++)
    {if(a[i]!=b[i])
       dc++;
    }
   return dc;   
}
int prime(){
   int v,count=0,d[2002];
   int min;
   int flag[2002];
   memset(flag,0,sizeof(flag));
   for(int i=0;i<n;i++)
     d[i]=dist[0][i];
   flag[0]=1;//先加入第一个顶点 
   while(count<n-1){//找到n-1条边（结束）
      min=0x7fffffff;// 2147483647为int类型能表示的最大数
      for(int j=1;j<n;j++){
        if(!flag[j]&& d[j]<min){
            min=d[j];
            v=j;                        
        }                 
      } 
      sum+=min;
      flag[v]=1;//顶点v加入
      for(int j=0;j<n;j++)//更新权重
        if(!flag[j]&&d[j]>dist[v][j])
          d[j]=dist[v][j]; 
      count++;
      
   } 
   return sum;  
}
int main(){
    while(cin>>n&&n){
        sum=0;
        for(int i=0;i<n;i++)
           scanf("%s",ch[i]);
         for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
             if(i==j)
                 dist[i][j]=0;
               else
                dist[i][j]=distance(ch[i],ch[j]);
         sum=prime();
         printf("The highest possible quality is 1/%d.\n",sum);                 
    }
    system("PAUSE");
    return 0;
}