【POJ 1789】Truck History（最小生成树）

题意：距离定义为两个字符串的不同字符的位置个数。然后求出最小生成树。

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2001;
const int M=4000001;
char code[N][10];
int f[N];//并查集
struct edge{
    int u,v,w;
}e[M];
int n,tot;
void add(int u,int v,int w){
    e[tot].u=u;e[tot].v=v;e[tot++].w=w;
}
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int x){
    if(f[x]==-1)return x;
    return f[x]=find(f[x]);
}
int Kruskal(){
    memset(f,-1,sizeof f);
    sort(e,e+tot,cmp);
    int cnt=0,ans=0;
    for(int i=0;i<tot;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        int fu=find(u),fv=find(v);
        if(fu!=fv){
            ans+=w;
            f[fu]=fv;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    return ans;
}
void solve(){
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    {
        int dis=0;
        for(int k=0;k<7;k++)
            if(code[i][k]!=code[j][k])dis++;
        add(i,j,dis);
    }
}
int main(){
    while(scanf("%d ",&n),n){
        tot=0;
        for(int i = 1; i <= n; i++)
            gets(code[i]);
        solve();
        printf("The highest possible quality is 1/%d.
", Kruskal());
    }
    return 0;
}