把每个字符串看成点,i和j的距离就是i串和j串中不同字符的个数。
#include<cstdio> #include<iostream> #include<cstring> #define INF 0x3f3f3f3f using namespace std; char str[2010][10]; int dis[2010],edge[2010][2010]; bool vis[2010]; int m,ans; int cmp(int x,int y) { int cnt=0; for(int i=0;i<7;i++) { if(str[x][i]!=str[y][i]) cnt++; } return cnt; } void prim() { int u=0,tmp; for(int i=0;i<m;i++) { dis[i]=edge[u][i]; } vis[u]=1; for(int j=1;j<m;j++) { tmp=INF; for(int i=1;i<m;i++) { if(!vis[i] && dis[i]<tmp) { tmp = dis[i]; u = i; } } vis[u]=1; //cout<<tmp<<endl; ans+=tmp; for(int i=0;i<m;i++) { if(!vis[i] && edge[u][i]<dis[i]) dis[i]=edge[u][i]; } } } int main() { while(scanf("%d",&m)!=EOF) { ans = 0; memset(vis,0,sizeof(vis)); if(m==0) break; for(int i=0;i<m;i++) scanf("%s",str[i]); for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { if(i==j) { edge[i][j]=edge[j][i]=0; continue; } edge[i][j]=edge[j][i]=cmp(i,j); // cout<<i<<' '<<j<<' '<<cmp(i,j)<<endl; } } prim(); printf("The highest possible quality is 1/%d.\n",ans); } return 0; }