poj1789

poj1789代码：

#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;
const int MAX=99999;
int N;
int dis[2001][2001];
char data[2001][8];
int distance( char *str1, char *str2)
{
	int d=0;
	for(int i=0;i<7;i++)
	{
		if(str1[i]!=str2[i])
			d++;
	
	}
	return d;
}
int visited[2002];
int rem[2002];
int prim()
{
	int sum=0;
        for(int i=0;i<N;i++)
	{
		visited[i]=0;
		rem[i]=dis[i][0];
	}
	visited[0]=1;
	for(int i=1;i<N;i++)
	{
		int min_index=-1;
		int min=MAX;
		for(int j=0;j<N;j++)
		{
			if(visited[j]==0&&rem[j]<min)
			{
				min=rem[j];
				min_index=j;
			}
		}
		if(min_index==-1)
		{
			printf("error!\n");
			exit(1);
		}
		visited[min_index]=1;
		sum+=min;
		for(int j=0;j<N;j++)
		{
			if(visited[j]==0&&rem[j]>dis[j][min_index])
			{
				rem[j]=dis[j][min_index];
			}
		}
	}
	return sum;

}

int main()
{
	freopen("input.txt","r",stdin);
	while(scanf("%d",&N)!=EOF)
	{
		if(N==0)
			break;

		for(int i=0;i<N;i++)
		{
			scanf("%s",&data[i]);
			//printf("%s\n",data[i]);
		}
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(i!=j)
				{
				       dis[j][i]=dis[i][j]=distance(data[i],data[j]);
				}
				else
				{
				      dis[i][j]=MAX;
				}				
			}
		}
		printf("The highest possible quality is 1/%d.\n",prim());
	}
       return 0;
}