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;
}