1574.txt

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

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 52
int a[7][3][3];
bool f[7];
const int n=6;
int st;
int max;
void input()
{

	int t[3];
	int i,j,k;
	for(i=1;i<=6;i++)
	{
		scanf("%d%d%d\n",&t[0],&t[1],&t[2]);
		for(k=0;k<3;k++)
			for(j=0;j<3;j++)
				a[i][k][j]=t[(k+j)%3];

		//?
	}
}
void tr(int y,int l,int v)
{
	if(y>n)
	{
		if(l==st)
		{
			if(v>max)
				max=v;
		}
		return ;
	}
	int i,j;

	for(i=1;i<=n;i++)
	{
		if(f[i])
			continue;
		for(j=0;j<3;j++)
		{
			if(1==y)
			{
				st=a[i][j][1];
				f[i]=1;
				tr(y+1,a[i][j][0],a[i][j][2]);
				f[i]=0;
			}
			else
			{
				if(a[i][j][1]!=l)
					continue;
				f[i]=1;
				tr(y+1,a[i][j][0],v+a[i][j][2]);
				f[i]=0;
			}
		}
	}
	return ;
}


	

void solve()
{
	memset(f,0,sizeof(f));
	max=-1;
	tr(1,-1,0);
	if(max==-1)
		printf("none\n");
	else
		printf("%d\n",max);
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	input();
	max=-1;
	char tc;
	while(1)
	{
		solve();
		scanf("%c",&tc);
		if(tc=='$')
			break;
		input();
	}
		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}