poj1789.zip_history

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,all; char a[2001][8]; int dis[4000005]; int p[2001]; int r[4000005]; int u[2001],v[2001]; int cmp(const int i,const int j){return dis[i]<dis[j];} int find(int x){return p[x]==x?x:p[x]=find(p[x]);} int kruskal() { int ans=0; for(int i=0;i<n;i++) p[i]=i; for(int i=0;i<all;i++) r[i]=i; sort(r,r+all,cmp); for(int i=0;i<all;i++) { int e=r[i]; int h=find(u[e]); int b=find(v[e]); if(h!=b) { ans+=dis[i]; p[b]=h; } } return ans; } int main() { while(cin>>n&&n!=0) { all=0; for(int i=0;i<n;i++) cin>>a[i]; int w=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) {w=0; for(int k=0;k<7;k++) if(a[i][k]!=a[j][k]) w++; u[all]=i;v[all]=j;dis[all]=w; all++; } cout<<"The highest possible quality is 1/"<<kruskal()<<'.'<<endl; } return 0; }