4667267_ac_329ms_15692k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 57 行

#include<iostream>
#define MAX 999999999
using namespace std;
int g[2001][2001];
int n;
void Create()       //创建图
{    
	int i,j,k,differ;    
	char s[2001][10];        
	for(i=0;i<n;i++)    
	{        
		cin>>s[i];        
		for(j=i-1;j>=0;j--)        
		{            
			differ=0;            
			for(k=0;k<7;k++)                
				if(s[i][k]!=s[j][k])                    
					differ++;            
				g[i][j]=g[j][i]=differ;        
		}        
		g[i][i]=0;    
	}
}
void Prim()       //生成最小生成树
{    
	int low[2001];    
	int i,j,k,min;        
	for(i=0;i<n;i++)        
		low[i]=g[0][i];        
	int sum=0;    
	for(i=1;i<n;i++)    
	{        
		min=MAX;        
		for(j=0;j<n;j++)            
		if(low[j]>0&&low[j]<min)            
		{                
			k=j;                
			min=low[j];            
		}        
		sum+=low[k];        
		low[k]=0;        
		for(j=0;j<n;j++)            
			if(g[k][j]!=0&&g[k][j]<low[j])                
				low[j]=g[k][j];    
	}    
	cout<<"The highest possible quality is 1/"<<sum<<"."<<endl;
}
int main()
{    
	while(cin>>n,n)    
	{        
		Create();        
		Prim();    
	}    
	return 0;
}