欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1789 Truck History G++

程序员文章站 2022-07-15 11:09:32
...

POJ 1789 Truck History G++

POJ 1789 Truck History G++

POJ 1789 Truck History G++

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//英语 看博友分析 
int fa[2008];
struct nod{
	int zhi;
	int x,y;
};
bool cmp(nod a, nod b)
{
	return a.zhi<b.zhi;
}
int find(int a)
{
	if(fa[a]==-1)
	{
		return a;
	}else
	{
		return fa[a]=find(fa[a]);
	}
}
int main()
{
	while(1)
	{
		int n;
		//cin>>n;
		scanf("%d",&n);
		if(n==0)
		{
			break;
		} 
		memset(fa,-1,sizeof(int)*(n+1));
		vector<string> ve;
		vector<nod> da;
		for(int i=0;i<n;i++)
		{
			char s[100];
			scanf("%s",s);
			string ts=s;
			ve.push_back(ts);
		}	
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				int js=0;
				for(int k=0;k<7;k++)
				{
					if(ve[i][k]!=ve[j][k])
					{
						js++;
					}
				}
				nod t;
				t.x=i;
				t.y=j;
				t.zhi=js;
				da.push_back(t);	
			}
		}	
		sort(da.begin(),da.end(),cmp);
		int jg=0;
		for(int i=0;i<da.size();i++)
		{
			int tx=da[i].x;
			int ty=da[i].y;
			int tz=da[i].zhi;
			tx=find(tx);
			ty=find(ty);
			if(tx!=ty)
			{
				fa[tx]=ty;
				jg=jg+tz;
			}
		}
		printf("The highest possible quality is 1/%d.\n",jg);
		//cout<<"The highest possible quality is 1/"<<jg<<"."<<endl;
	}
	return 0;
}