POJ1789&ZOJ2158--Truck History【最小生成树变形】

链接：http://poj.org/problem?id=1789

题意：卡车公司有悠久的历史，它的每一种卡车都有一个唯一的字符串来表示，长度为7，它的全部卡车（除了第一辆）都是由曾经的卡车派生出来的。如今一些砖家想研究这些卡车的历史，他们定义了卡车类型编码的距离：卡车编码字符串（长度7）同样位置字符不同的个数。比方一个卡车编码是aaaaaaa，还有一个是bbaaaaa，则他们的距离是2,。他们又定义了派生方案的优劣值：1/Σ,t)d(t,t)。

当中t0为基类型，td为派生类型，d（t0，td）为两个类型的卡车编码距离。

现给出卡车编码，求具有最高优劣值的派生方案。

这道题说的非常绕，看似非常麻烦，事实上能够转换成最小生成树。

要使优劣值最高，则公式的分母部分应该最小，假设把每种卡车编码理解成无向图的顶点，不同卡车编码间的距离理解成无向边的权值，则分母部分就是最小生成树的权值。这样转换这道题就好做了。

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 2010

#define eps 1e-7

#define INF 0x7FFFFFFF

#define seed 131

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int edge[MAXN][MAXN],vis[MAXN],dist[MAXN];

int n,m,ans;

char st[MAXN][10];

void prim(){

    int i,j;

    memset(vis,0,sizeof(vis));

    vis[1] = 1;

    for(i=1;i<=n;i++)   dist[i] = edge[1][i];

    for(i=0;i<n-1;i++){

        int temp = INF,k = -1;

        for(j=1;j<=n;j++){

            if(!vis[j]&&dist[j]<temp){

                temp = dist[j];

                k = j;

            }

        }

        if(k==-1)   break;

        vis[k] = 1;

        ans += dist[k];

        for(j=1;j<=n;j++){

            if(!vis[j]&&edge[k][j]<dist[j])

                dist[j] = edge[k][j];

        }

    }

}

int main(){

    int i,j;

    while(scanf("%d",&n),n){

        ans = 0;

        for(i=0;i<n;i++){

            scanf("%s",st[i]);

        }

        for(i=0;i<n;i++){

            for(j=i+1;j<n;j++){

                int x = 0;

                for(int ii=0;ii<7;ii++){

                    if(st[i][ii]!=st[j][ii])    x++;

                }

                edge[i+1][j+1] = edge[j+1][i+1] = x;

            }

            edge[i+1][i+1] = 0;

        }

        prim();

        printf("The highest possible quality is 1/%d.\n",ans);

    }

    return 0;

}