题目大意是就是给出n个长度为7的字符串，每个字符串代表一个车，定义车的距离是两个字符串间不同字母的个数，题目要求的数不同的车的距离的最小值，即所求的就是最小生成树
Sample Input
4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output
The highest possible quality is 1/3. //输出 1/权值之和
prim
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 # define LL long long 7 using namespace std ; 8 9 const int INF=0x3f3f3f3f; 10 const int MAXN=2010; 11 bool vis[MAXN]; 12 int lowc[MAXN]; 13 int n ; 14 int cost[MAXN][MAXN] ; 15 char s[2010][10] ; 16 17 int Prim()//点是0~n-1 18 { 19 int ans=0; 20 memset(vis,false,sizeof(vis)); 21 vis[0]=true; 22 for(int i=1;i<n;i++)lowc[i]=cost[0][i]; 23 for(int i=1;i<n;i++) 24 { 25 int minc=INF; 26 int p=-1; 27 for(int j=0;j<n;j++) 28 if(!vis[j]&&minc>lowc[j]) 29 { 30 minc=lowc[j]; 31 p=j; 32 } 33 if(minc==INF)return -1;//原图不连通 34 ans+=minc; 35 vis[p]=true; 36 for(int j=0;j<n;j++) 37 if(!vis[j]&&lowc[j]>cost[p][j]) 38 lowc[j]=cost[p][j]; 39 } 40 return ans; 41 } 42 43 int main() 44 { 45 46 // freopen("in.txt","r",stdin) ; 47 while(scanf("%d" , &n) !=EOF) 48 { 49 if (n == 0) 50 break ; 51 int w ; 52 int i , j ,k ; 53 for (i = 0 ; i < n ; i++) 54 for (j = 0 ; j < n ; j++) 55 cost[i][j] = INF ; 56 for (i = 0 ; i < n ; i++) 57 scanf("%s" , s[i]); 58 for (i = 0 ; i < n ; i++) 59 for (j = i+1 ; j < n ; j++) 60 { 61 w = 0 ; 62 for (k = 0 ; k < 7 ; k++) 63 { 64 if (s[i][k] != s[j][k]) 65 w++ ; 66 } 67 cost[i][j] = w ; 68 cost[j][i] = w ; 69 } 70 printf("The highest possible quality is 1/%d. ",Prim()); 71 72 73 } 74 return 0 ; 75 }