大意：用一个7位的string代表一个编号，两个编号之间的距离代表这两个编号之间不同字母的个数。一个编号只能由另一个编号变化的来，变化的字母的数量就是这两个编号之间相应的距离，现在要找出一个变化方案，使得总代价最小，也就是距离之和最小。
思路：将每个字符串当成一个节点，求出每个节点之间需要变化的次数为边的权值，用Prim建立最小生成树（稠密图）。
1 #include <stdio.h> 2 #include <string.h> 3 #define INF 0x3f3f3f3f 4 5 int Map[2010][2010]; 6 char s[2010][8]; 7 int dis[2010]; 8 int n; 9 10 int min(int a, int b) 11 { 12 return a > b ? b : a; 13 } 14 15 int length(int i, int j) 16 { 17 int cnt = 0; 18 for(int k = 0; k < 7; k++) 19 { 20 if(s[i][k] != s[j][k]) 21 cnt++; 22 } 23 return cnt; 24 } 25 26 int Prim() 27 { 28 int Ans; 29 int Min_ele, Min_node; 30 memset(dis, INF, sizeof(dis)); 31 Ans = 0; 32 int r = 1; 33 for(int i = 1; i <= n-1; i++) 34 { 35 Min_ele = INF; 36 dis[r] = -1; 37 for(int j = 1; j <= n; j++) 38 { 39 if(dis[j] >= 0) 40 { 41 dis[j] = min(dis[j], Map[r][j]); 42 if(dis[j] < Min_ele) 43 { 44 Min_ele = dis[j]; 45 Min_node = j; 46 } 47 } 48 } 49 r = Min_node; 50 Ans += Min_ele; 51 } 52 return Ans; 53 } 54 55 void Solve() 56 { 57 while(~scanf("%d%*c", &n) && n) 58 { 59 for(int i = 1; i <= n; i++) 60 { 61 scanf("%s", s[i]); 62 } 63 memset(Map, 0, sizeof(Map)); 64 for(int i = 1; i <= n-1; i++) 65 { 66 for(int j = i+1; j <= n; j++) 67 { 68 Map[i][j] = Map[j][i] = length(i, j); 69 } 70 } 71 printf("The highest possible quality is 1/%d.\n", Prim()); 72 } 73 } 74 75 int main() 76 { 77 Solve(); 78 79 return 0; 80 }