POJ - 1789
题意分析：给出n个长度为7的字符串，每个字符串代表一个车，定义车的距离是两个字符串对应位置间不同字母的个数，要求输出不同车距离的最小值，也就是求最小生成树。
分析：这道题的关键就是找出每两个车之间的距离，即每两个字符串相同位置的不同字母的个数。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2010;
char s[N][10];
int e[N][N],dis[N],vis[N];
int n;
void prim()
{
memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) dis[i]=e[1][i];dis[1]=0;vis[1]=1;int ans=0;for(int i=1;i<=n-1;i++){
int minn=0x3f,u;for(int j=1;j<=n;j++){
if(!vis[j]&&minn>dis[j]){
u=j;minn=dis[j];} } ans+=minn;vis[u]=1;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>e[u][j])dis[j]=e[u][j];}printf("The highest possible quality is 1/%d.\n",ans);
}
int main()
{
while(scanf("%d",&n)&&n){
memset(e,0x3f,sizeof e);for(int i=1;i<=n;i++) scanf("%s",s[i]);for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int cnt=0; for(int k=0;k<7;k++)if(s[i][k]!=s[j][k])cnt++; e[i][j]=e[j][i]=cnt;}}prim();}return 0;
}