zoj 2158 prim

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define INF 1000000
#define MAXN 2000
int N;
char codes[MAXN][10];
int d[MAXN][MAXN];
int lowcost[MAXN];
int prim()
{
	int i, j, k;
	int dist;
	memset( d, 0, sizeof(d) );
	for( i = 0; i < N; i++ )
	{
		for( j = i+1; j < N; j++ )
		{
			dist = 0;
			for( k = 0; k < 7; k++ )
                if(codes[j][k]!= codes[i][k])
                dist++;
			 d[i][j] = d[j][i] = dist;
		}
	}
	int sum = 0;
	lowcost[0] = -1;
	for( i = 1; i < N; i ++ )
		lowcost[i] = d[0][i];
	for( i = 1; i < N; i++ )
	{
		int min = INF;
		for( k = 0; k < N; k++ )
		{
			if( lowcost[k] != -1  &&  lowcost[k] < min )
			{
				j = k;
				min = lowcost[k];
			}
		}
		sum += min;
		lowcost[j] = -1;
		for( k = 0; k < N; k ++ )
		{
			if( d[j][k] < lowcost[k] )
				lowcost[k] = d[j][k];
		}
	}
	return sum;
}
int main()
{
	int i;
//	freopen("1.txt","r",stdin);
	while( 1 )
	{
		scanf( "%d", &N );
		if( N==0 )
            break;
		for( i = 0; i < N; i++ )
			scanf( "%s", codes[i] );
		printf( "The highest possible quality is 1/%d.\n", prim());
	}
	return 0;
}