学步园

//poj1789 抄别人kruskal代码始终让我不爽，决定至少用prime过这道题。 
//开一个距离表维护所有未加入党组织的点到党组织的距离。
//每次吸纳最短成员，更新这个距离表 

//原来时间限制是2000MS，这题目现在是1344MS过 

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAX 2005
#define inf 1001
using namespace std;
string code[2005];
bool mark[2005];
int top = 0;
int dist[2005];
int sum;
int CC(string a, string b)
{
	int ret = 0;
	for(int i = 0; i < (int)a.length(); i++)
		if(a[i] != b[i])
			ret++;
	return ret;
}
int prime(int n)
{
	//任意选取一点开始 
	dist[0] = 0;
	mark[0] = true; 
	for(int i = 1; i < n; i++)
	{
		dist[i] = CC(code[0], code[i]);
	}
	for(int i = 1; i < n;  i++)
	{
		int min1 = inf;
		int minIndex = -1;
		//寻找未访问并且距离党组织最短距离的顶点 
		for(int j = 1; j < n; j++)
		{
			if(!mark[j] && dist[j] < min1)
			{
				min1 = dist[j];
				minIndex = j;
			}
		}
		//加入并更新 
		sum += dist[minIndex];
		dist[minIndex] = 0;
		mark[minIndex] = true;
		for(int j = 1; j < n; j++)
		{
			if(!mark[j])
				dist[j] = (CC(code[minIndex], code[j]) < dist[j])? CC(code[minIndex], code[j]):dist[j];
		}
	}
	return sum;
}
int main()
{
	int n;
	cin>>n;
	while(n)
	{
		getchar();
		top = 0;
		sum = 0;
		memset(mark, 0, sizeof(mark));
		memset(dist, inf, sizeof(dist));
		for(int i = 0; i < n; i++)
		{
			getline(cin, code[i]);
		}
	 	int res = prime(n);
	 	cout<<"The highest possible quality is 1/"<<res<<"."<<endl;
		cin>>n;
	}
	return 0;
}