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

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

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

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

POJ1789&ZOJ2158--Truck History【最小生成树变形】,布布扣,bubuko.com

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

原文：http://blog.csdn.net/zzzz40/article/details/38374195