#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge
{
int row;
int column;
int value;
Edge()
{}
Edge( int a, int b, int c )
:row(a),column(b),value(c)
{}
};
bool operator<( Edge const& Itema, Edge const& Itemb )
{
return Itema.value> Itemb.value;
}
vector<Edge> graph;
int visite[2001];
char ch[2001][8];
int find( int x )
{
if ( x!= visite[x] )
return find( visite[x] );
return x;
}
int distance( char str1[8], char str2[8] )
{
int num= 0;
for ( int i= 0; i< 8; ++i )
if ( str1[i]!= str2[i] )
num++;
return num;
}
int main()
{
int n;
while ( scanf("%d",&n), n )
{
for ( int i= 0; i< n; ++i )
scanf("%s",ch[i] );
graph.reserve ( n+ 1 );
for ( int i= 0; i< n; ++i )
{
for ( int j= 0; j< i; ++j )
graph.push_back ( Edge( j,i,distance( ch[i], ch[j] ) ) );
visite[i]= i;
}
make_heap( graph.begin (), graph.end () );
int sum= 0;
int num= 1;
while ( num< n )
{
int u,v;
if ( (u= find(graph[0].column))!= (v= find(graph[0].row ) ) )
{
sum+= graph[0].value;
visite[v]= u;
num++;
}
pop_heap( graph.begin (), graph.end () );
graph.pop_back ();
}
printf( "The highest possible quality is 1/%d.\n", sum );
graph.clear ();
}
return 0;
}posted on 2008-11-06 12:00
Darren 閱讀(248)
評論(3) 編輯 收藏 引用