1833.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1833 on 2006-03-01 at 13:13:20 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 2560;
const int MAX_LEN = 8;
const int INFINITE = 60000;

char code[MAX][MAX_LEN];

int dis(int, int);
int Prim(int);

int main()
{
	int n, i;
	
	while(scanf("%d\n", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) gets(code[i]);
		printf("The highest possible quality is 1/%d.\n", Prim(n));
	}
	
	return 0;
}

int dis(int n, int m)
{
	int i, p = 0;
	
	for(i = 0; i < MAX_LEN; i++)
		if(code[n][i] != code[m][i]) p++;
	return p;
}
int Prim(int n)
{
	bool inTree[MAX] = { false };
	int i, j, d[MAX], total = 0;
	
	d[0] = 0; inTree[0] = true;
	for(i = 1; i < n; i++) d[i] = dis(0, i);
	for(i = 1; i < n; i++) {
		int mind = INFINITE, mini;
		for(j = 0; j < n; j++) {
			if(!inTree[j] && d[j] < mind) {
				mind = d[j]; mini = j;
			}
		}
		inTree[mini] = true; total += d[mini];
		for(j = 0; j < n; j++)
			if(!inTree[j]) d[j] = min(d[j], dis(mini, j));
	}
	return total;
}