http://poj.org/problem?id=1789
读不懂题再简单也不会做，英语是硬伤到哪都是真理，sad++。
此题就是一个最小生成树，两点之间的权值是毎两串之间的不同字母数。
#include<stdio.h>
#include<string.h>
const int N=;
const int INF=<<;
int map[N][N],vis[N],dis[N];
int n,sum;
void prim()
{
int pos;
for (int i = ; i <= n; i ++)
{
dis[i] = map[][i];
}
vis[] = ;
for (int i = ; i <= n-; i ++)
{
int min = INF;
for (int j = ; j <= n; j ++)
{
if (!vis[j] && dis[j] < min)
{
min = dis[j];
pos = j;
}
}
sum += min;
vis[pos] = ;
for (int j = ; j <= n; j ++)
{
if (!vis[j] && dis[j] > map[pos][j])
dis[j] = map[pos][j];
} }
}
void init()
{
sum = ;
for (int i = ; i <= n; i ++)
{
for (int j = ; j <= n; j ++)
{
map[i][j] = INF;
}
map[i][i] = ;
vis[i] = ;
} }
int main()
{
char str[N][];
int cnt;
while(~scanf("%d",&n)&&n)
{ init();
for (int i = ; i <= n; i ++)
{
scanf("%s",str[i]+);
}
for (int i = ; i <= n; i ++)
{
for (int j = i+; j <= n; j ++)
{
cnt = ;
for (int k = ; k <= ; k ++)
{
if (str[i][k]!=str[j][k])
cnt++;
}
map[i][j] = cnt;
map[j][i] = cnt;
}
}
prim();
printf("The highest possible quality is 1/%d.\n",sum);
}
return ; }