题意：给你n辆车，每辆车有7个字符的编号，他们之间的距离值等于他们中不同字符的位置数目，然后叫你求最高优劣值的派生方案 1/Q，Q就要最小，求最小生成树
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 #define inf 999999 8 #define N 2013 9 int n,dis[N],vis[N],g[N][N]; 10 char s[N][10]; 11 12 int prim(int st) 13 { 14 for(int i=1; i<=n; i++) 15 { 16 dis[i] = g[i][st]; 17 vis[i] = 0; 18 } 19 dis[st] = 0 ; vis[st] = 1; 20 int cost = 0; 21 for(int T=1; T<n; T++) 22 { 23 int mindis = inf ,idx = -1; 24 for(int i=1; i<=n; i++) 25 { 26 if(!vis[i] && dis[i] < mindis) 27 { 28 mindis = dis[i]; 29 idx = i; 30 } 31 } 32 cost += mindis; 33 if(idx==-1) return -1; 34 vis[idx] = 1; 35 for(int i=1; i<=n; i++) 36 { 37 if(!vis[i] && dis[i] > g[i][idx]) 38 dis[i] = g[i][idx]; 39 } 40 } 41 return cost; 42 } 43 44 int main() 45 { 46 while(scanf("%d",&n)&&n) 47 { 48 for(int i=1; i<=n; i++) 49 for(int j=1; j<=n; j++) 50 { 51 if(i==j) g[i][j] = 0; 52 else g[i][j] = inf; 53 } 54 for(int i=1; i<=n; i++) 55 cin>>s[i]; 56 for(int i=1; i<=n; i++) 57 { 58 for(int j=i+1; j<=n; j++) 59 { 60 int cnt = 0; 61 for(int k=0; k<7; k++) 62 { 63 if(s[i][k]!=s[j][k]) 64 cnt++; 65 } 66 g[i][j] = g[j][i] = cnt; 67 } 68 } 69 printf("The highest possible quality is 1/%d. ",prim(1)); 70 } 71 return 0; 72 }