学步园

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;
#define MAX 2005
char str[MAX][8];
int n,father[MAX],rank[MAX],k;//k为边数

struct node{
      int st;
      int en;
      int we;
}edge[MAX*MAX/2];

/*bool cmp1(node a,node b)
{
    return a.we<b.we;
}*/
int cmp(const void *a,const void *b)
{
    return ((node*)a)->we-((node*)b)->we;
}

int Weight(int i,int j)
{
    int m=0;
    int w=0;
    while(m<7)
    {
        if(str[i][m]!=str[j][m])
            w++;
        m++;
    }
    return w;
}

//并查集
void make_set()
{
    int i;
    for(i=0; i<MAX; i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}

int find_set(int x)
{
    if(father[x]!=x)
        father[x]=find_set(father[x]);
    return father[x];
}

bool Union(int x,int y)
{
    int px=find_set(x);
    int py=find_set(y);
    if(px!=py)
    {
        if(rank[px]>rank[py])
        {
            father[py]=px;
        }
        else
        {
           if(rank[px]==rank[py])
                rank[py]++;
           father[px]=py;
        }
        return true;
    }
    return false;
}

int Kruskal()
{
    int i,cost=0,nCount=0;
    for(i=0; i<k; i++)
    {
        int start,end;
        start=edge[i].st;
        end=edge[i].en;
        if(Union(start,end))
        {
            cost+=edge[i].we;
        }
    }
    return cost;
}

int main()
{
    int i,j;
    //freopen("acm.txt","r",stdin);
    while(scanf("%d",&n)!=EOF && n)
    {
    make_set();
    getchar();
    for(i=0; i<n; i++)
    {
        scanf("%s",str[i]);
    }
    k=0;
    for(i=0; i<n-1; i++)
    {
        for(j=i+1; j<n; j++)
        {
            edge[k].st=i;
            edge[k].en=j;
            edge[k++].we=Weight(i,j);
        }
      }
    //sort(edge,edge+k,cmp1);
    qsort(edge,k,sizeof(node),cmp);
    printf("The highest possible quality is 1/%d.\n",Kruskal());
    }
    return 0;
}