2088.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"algorithm"

int dis[21][21];
int tim[21],n;
int id[21],mint[21];

int cmp(int a,int b)
{
	return mint[a]<mint[b];
}

void init()
{
	int i,j,k;
	for(i=0;i<n;i++)
	cin>>tim[i];
	
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{
		cin>>dis[i][j];
	}
	
	for(k=0;k<n;k++)
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	if(dis[i][k]+dis[k][j]<dis[i][j])
	dis[i][j]=dis[i][k]+dis[k][j];
	
	for(i=0;i<n;i++)
	{
		mint[i]=9999;id[i]=i;
		for(j=0;j<n;j++)
		{
			dis[j][i]+=tim[i];
			if(dis[j][i]<mint[i])mint[i]=dis[j][i];
		}
	}
	std::sort(&id[0],&id[n],cmp);

}

long answer;
long visit;
int ll;
bool find(int a,int s,int rest)
{
	long k;int i,t,limit=5;
	
	if(s>answer)answer=s;
	
	if(answer==n)return 1;
	visit^=1<<a;

	t=0;
	for(i=0;t<=rest&&i<n;i++)
	if(!(visit&(1<<id[i])))
	{
		t+=mint[id[i]];
	}
	
	if(i+s<answer)return 0;

	for(i=0;i<n&&limit;i++)
	{
		if(!(visit&(1<<i))&&rest>=dis[a][i])
		{
			limit--;
			if(find(i,s+1,rest-dis[a][i]))return 1;
		}
	}
		
	visit^=1<<a;
	
	return 0;
}

int main()
{
	int i,t,c=1;

	while(1)
	{
		cin>>n;
		if(n==0)break;
		init();
		
		answer=0;
		for(i=0;i<n;i++)
		if(420>=tim[i])
		{
			visit=0;
			t=find(i,1,420-tim[i]);
		}
		
		cout<<answer<<endl;
	}
	return 0;
}