学步园

 poj 1789 Truck History

#include <iostream>
using namespace std;
char a[2001][8];
int n;
int w[2001][2001];
bool f[2001];
int lowcost[2001];
int prim(){
    int i,j;
    memset(f,0,sizeof(f));
    memset(lowcost,0,sizeof(lowcost));
    f[1]=1;
    for(i=1;i<=n;i++)
    lowcost[i]=w[1][i];
    int ans=0;
    for(i=1;i<n;i++){
        int v;
        int min=100*100*127;
        for(j=1;j<=n;j++){
            if(f[j]==0&&lowcost[j]<min){
                min=lowcost[j];
                v=j;
                }
            }
        ans+=min;
        f[v]=1;
        for(j=1;j<=n;j++){
            if(f[j]==0&&w[v][j]<lowcost[j])
            lowcost[j]=w[v][j];
            }
        }
    return ans;
    }
int main(){
    while(cin>>n&&n!=0){
        int i,j,k;
        memset(w,0,sizeof(w));
        for(i=1;i<=n;i++){
            for(j=1;j<=7;j++)
            cin>>a[i][j];
            }
        for(i=1;i<n;i++){
            for(j=i+1;j<=n;j++){
                for(k=1;k<=7;k++){
                    if(a[i][k]!=a[j][k]){
                        w[i][j]++;
                        w[j][i]++;
                        }
                    }
                }
            }
        cout<<"The highest possible quality is 1/"<<prim()<<"."<<endl;
        }
    return 0;
}