poj 1789 Truck History 最小生成树 prim

#include <iostream>
#include <cstring>

using namespace std;
char str[2001][9];
int d[2001][2001];
int mind[2001];//mind restore the min distance of the point between the tree when the point hasn‘t been add into
//rather than the point in the tree to all the point not in the  tree
bool vis[2001];
int n;
int ans;
int index;
void setd(){
    for(int i=0;i<n;i++){
        d[i][i]=0;
        for(int j=i+1;j<n;j++){
            d[i][j]=d[j][i]=0;
            for(int k=0;k<7;k++){
                if(str[i][k]!=str[j][k]){
                    d[i][j]++;
                }
            }
            d[j][i]=d[i][j];
        }
    }
}
void prim(){
    memset(mind,0x3f,sizeof(mind));
    memset(vis,0,sizeof(vis));
    index=1;
    vis[0]=true;
    ans=0;
    int s=0;
    while(index<n){
        int minnum=0x3f3f;
        int mini=0;
        for(int i=0;i<n;i++){
            if(!vis[i]&&d[s][i]<mind[i]){
                mind[i]=d[s][i];//use i to refresh all the point
            }
            if(!vis[i]&&mind[i]<minnum){
                minnum=mind[i];
                mini=i;
            }
        }
        ans+=minnum;
        vis[mini]=true;
        s=mini;
        index++;
    }
}
int main(){
ios::sync_with_stdio(false);
    while(cin>>n&&n){
        for(int i=0;i<n;i++){
            cin>>str[i];
        }
        setd();
        prim();
        cout<<"The highest possible quality is 1/"<<ans<<".\n";
    }

    return 0;
}