POJ1789 Truck History

题目链接: [ kuangbin带你飞 专题六 最小生成树 F - Truck History

](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/F)

题意

英语不好,看题好费劲,大概意思是:
一个汽车公司每个卡车都用一个长度为7的字符串来表示,每个卡车之间都可以进行派生,而且派生会有代价
A : aaaaaaa
B : baaaaab
A车和B车有两个地方不同,所以它们之间派生的代价是2
问以任意一个卡车开始,依次派生出所有卡车,需要的最小代价是多少

思路

题目分类就是最小生成树,很明确,题目意思看懂后,也很好理解,将车看做点,互相之间派生以及代价可看做无向有权边,然后求最小生成树,prim即可

代码

//
//  main.cpp
//  demo
//
//  Created by shiyi-mac on 16/1/2.
//  Copyright © 2016年 shiyi-mac. All rights reserved.
//
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

const int N = 2009;
const int MAX = 1000000;
int g[N][N];
int d[N], p[N];
char s[N][7];

int prim(int n)
{
    for(int i=2;i<=n;i++)
        d[i] = g[1][i];
    d[1] = -1;
    int ans = 0;
    for(int i=1;i<n;i++)
    {
        int min = MAX;
        int imin = -1;
        for(int j=1;j<=n;j++)
            if(d[j]!=-1 && min > d[j])
                min = d[j], imin = j;
        ans += min;
        //cout<<min<<"=="<<imin<<endl;
        d[imin] = -1;
        for(int j=1;j<=n;j++)
            if(d[j]!=-1 && d[j] > g[imin][j])
                d[j] = g[imin][j];
    }
    return ans;
}

int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        memset(g, 0, sizeof(g));
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                for(int k=0;k<7;k++)
                    if(s[i][k] != s[j][k])
                        g[i][j]++, g[j][i]++;
            }
        printf("The highest possible quality is 1/%d.\n", prim(n));
    }
    return 0;
}