poj1789:http://poj.org/problem?id=1789
题意大概是这样的：用一个7位的string代表一个编号，两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来，代价是这两个编号之间相应的distance，现在要找出一个“衍生”方案，使得总代价最小，也就是distance之和最小。
题解：问题可以转化为最小代价生成树的问题。因为每两个结点之间都有路径，所以是完全图。 此题的关键是将问题转化为最小生成树的问题。每一个编号为图的一个顶点，顶点与顶点间的编号差即为这条边的权值，题目所要的就是我们求出最小生成树来。这里我用prim算法来求最小生成树。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 100000000
using namespace std;
int g[][];
int sum,n;
int lowcost[];
struct Node{
char ss[];
}node[];
int juli(Node a,Node b){
int count=;
for(int i=;i<;i++){
if(a.ss[i]!=b.ss[i])
count++;
}
return count;
}
void prim(int v0){
sum=;
for(int i=;i<=n;i++){
lowcost[i]=g[v0][i];
}
lowcost[v0]=-;
for(int i=;i<n;i++){
int min=INF;
int v=-;
for(int j=;j<=n;j++){
if(lowcost[j]!=-&&lowcost[j]<min){
v=j;min=lowcost[j];
}
}
if(v!=-){
sum+=lowcost[v];
lowcost[v]=-;
for(int k=;k<=n;k++){
if(lowcost[k]!=-&&g[v][k]<lowcost[k])
lowcost[k]=g[v][k];
}
}
}
printf("The highest possible quality is 1/%d.\n",sum);
}
int main(){
while(~scanf("%d",&n)&&n){
for(int i=;i<=n;i++)
scanf("%s",node[i].ss);
for(int i=;i<=n;i++)
for(int j=+i;j<=n;j++){
g[i][j]=g[j][i]=juli(node[i],node[j]);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(i==j)g[i][j]=;
else if(g[i][j]==)g[i][j]=INF; prim();
}
}