//11163000 c00h00g 1789 Accepted 15844K 657MS G++ 1411B 2013-01-07 12:35:43 用kruskal的话需要计算边的个数没有prim方便 #include<stdio.h> #include<stdlib.h> #include<string.h> int N; char input[2005][8]; int quality(const char* a,const char* b){ int res=0; for(int i=0;i<7;i++){ if(a[i]!=b[i]) res++; } return res; } int dis[2005][2005]; int d[2005]; int vis[2005]; //起点设置为0 int main(){ while(scanf("%d",&N)!=EOF){ if(N==0) break; memset(vis,0,sizeof(vis)); for(int i=0;i<N;i++) scanf("%s",input[i]); for(int i=0;i<N;i++) for(int j=0;j<N;j++){ if(i==j) dis[i][j]=0; else dis[i][j]=quality(input[i],input[j]); } for(int i=0;i<N;i++) d[i]=dis[0][i]; vis[0]=1; //循环次数 int min,v,res=0; for(int i=0;i<N-1;i++){ min=10000; //寻找最小值 for(int j=0;j<N;j++){ if(vis[j]==0&&d[j]<min){ min=d[j]; v=j; } } vis[v]=1; res+=min; //更新 for(int j=0;j<N;j++){ if(vis[j]==0&&dis[v][j]<d[j]){ d[j]=dis[v][j]; } } } printf("The highest possible quality is 1/%d.\n",res); } return 0; }