4667209_ac_1391ms_15760k.cpp

部分PKU上的源码

#include<iostream>
#include<string>
#define MAXNUM 765432100
using namespace std;
int n;
string input[2005];
int map[2005][2005];
int dis[2005];
int length;
bool used[2005];
int pickmin()
{
	int tmin=MAXNUM,re=0;
	for(int count=1;count<=n;count++)
	{
		if(dis[count]<tmin&&used[count]==false)
		{
			tmin=dis[count];
			re=count;
		}
	}
	return re;
}
void prim()
{
	int count;
	for(count=1;count<=n;count++)
	{
		dis[count]=map[1][count];
	}
	memset(used,false,sizeof(used));
	length=0;
	used[1]=true;
	int all=1;
	do
	{
		int temp=pickmin();
		if(temp!=0)
		{
			used[temp]=true;
			length+=dis[temp];
			for(count=1;count<=n;count++)
			{
				if(map[temp][count]<dis[count]) dis[count]=map[temp][count];
			}
		}
		else break;
	}while(all<n);
	printf("The highest possible quality is 1/%d.\n",length);
}
int bijiao (string x,string y)
{
	int re=0;
	for(int count=0;count<x.size();count++)
	{
		if(x[count]!=y[count]) re++;
	}
	return re;
}
int main()
{
	while(cin>>n)
	{
		if(n==0) return 0;
		for(int count=1;count<=n;count++)
		{
			cin>>input[count];
			for(int i=1;i<count;i++)
			{
				int temp=bijiao(input[count],input[i]);
				map[i][count]=temp;
				map[count][i]=temp;
			}
			map[count][count]=MAXNUM;
		}
		prim();
	}
	return 0;
}