poj 1789 Truck History prim 최소 생성 트리 베이스!!!

1506 단어
제목의 뜻은 트럭의 차이를 연구하면 각 트럭의 7자리 번호를 매긴 다음에 그들 중 몇 명이 다르다는 것을 보면 그들의 차이는 몇 개이다. 그리고 그들이 연결할 수 있는 최소한의 거리와 거리를 구한다.
#include<iostream>
using namespace std;
int map[2002][2002],vis[2002],dis[2002],sum;
char a[2002][10];int n;
void prim(int k)
{
	int temp;
	for(int i=1;i<=n;i++)
	dis[i]=map[k][i];
	vis[k]=1;
	for(int i=1;i<=n;i++)
	{
		int cf=0x7FFFFFFF;
		for(int j=1;j<=n;j++)
		if(!vis[j]&&dis[j]<cf)
		{
			temp=j;
			cf=dis[j];
		}
		if(cf==0x7FFFFFFF)
		cf=0;
		sum+=cf;
		vis[temp]=true;
		for(int j=1;j<=n;j++)
		if(!vis[j]&&map[temp][j]<dis[j])
		dis[j]=map[temp][j];
	}
}
int main()
{
	
	while(cin>>n,n)
	{
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			map[i][j]=0x7FFFFFFF;
			vis[i]=0;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(i!=j)
				{
					int cou=0;
					for(int k=0;k<7;k++)
					if(a[i][k]!=a[j][k])
					cou++;
					map[i][j]=map[j][i]=cou;
				}
			}
		}
		sum=0;
		prim(1);
		printf("The highest possible quality is 1/%d.
",sum); } return 0; }

좋은 웹페이지 즐겨찾기