POJ1789（最小生成树,kruskal算法）

 由于和结点联系非常密切，所以容易想到使用kruskal算法。

题意：编写程序输出最高质量的火车推导计划。火车推倒计划质量的求解公式中的分子为1，分母为t0,td的距离总和。

t0,td的距离就是两个输入字符串的字母不同位置的个数。想要推导计划的质量最高就是使分母最小。即t0,td的距离总和最小。

实质上是以任意两个字符串为结点，以字符串字母不同位置的个数为两节点之间边的权值，求解最小生成树。因此输入和结点联系密切，使用kruskal算法求解比较方便。

下面是AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn][7];
int pre[maxn];
struct truck
{int to;int from;int weight;
} pp[maxn*(maxn>>1)];
int n,qq,ans;
void init()
{ans=0;qq=0;for(int i=0; i<=n; i++)pre[i]=i;
}
bool cmp(truck a,truck b)
{return a.weight<b.weight;
}
int finds(int x)
{if(x==pre[x])return pre[x];pre[x]=finds(pre[x]);return pre[x];
}
void make_tree()
{for(int i=0; i<n; i++)for(int j=n-1; j>=i; j--){int sum=0;for(int x=0; x<7; x++)if(str[i][x]!=str[j][x])sum++;pp[qq].from=i;pp[qq].to=j;pp[qq].weight=sum;++qq;}
}
void kruskal()
{sort(pp,pp+qq,cmp);int to,from;for(int i=0; i<qq; i++){to=finds(pp[i].to);from=finds(pp[i].from);if(to==from);else if(to!=from){pre[to]=from;ans+=pp[i].weight;}}
}
int main()
{while(~scanf("%d",&n)&&n){for(int i=0; i<n; i++)scanf("%s",str[i]);init();make_tree();kruskal();printf("The highest possible quality is 1/%d.\n",ans);}return 0;
}