POJ1789.md

prim跑MST即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
const int MAXN = 2222;
int n;
char s[MAXN][10];
int G[MAXN][MAXN],dist[MAXN];
int main(){
    while(scanf("%d",&n)!=EOF && n){
        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++){
                int tot = 0;
                for(int k = 0; k < 7; k++) if(s[i][k]!=s[j][k]) tot++;
                G[i][j] = G[j][i] = tot;
            }
            G[i][i] = 0;
        }
        memset(dist,0x3f,sizeof(dist));
        dist[1] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
        que.push(make_pair(dist[1],1));
        int ans = 0;
        while(!que.empty()){
            pair<int,int> tp = que.top();
            que.pop();
            if(dist[tp.second]!=tp.first) continue;
            ans += tp.first;
            for(int i = 1; i <= n; i++){
                if(G[tp.second][i]<dist[i]){
                    dist[i] = G[tp.second][i];
                    que.push(make_pair(dist[i],i));
                }
            }
        }
        printf("The highest possible quality is 1/%d.\n",ans);
    }
    return 0;
}