1041.txt

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

//#define debug 1
#define NMAX 46
#define INF 1000000001
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>


int p[NMAX];
int a[NMAX][NMAX*NMAX];
int n;
typedef struct
{
	int v;
	int x,y;
}data;
data edge[NMAX*NMAX];
int ek;
void add(int x,int y,int z)
{
	int l,r,i;
	l=0;
	while(p[l])
	{
		if(p[l]==x)
		{
			break;
		}
		l++;
	}
	if(!p[l])
	{
		p[l]=x;
	}
	r=0;
	while(p[r])
	{
		if(p[r]==y)
		{
			break;
		}
		r++;
	}
	if(!p[r])
	{
		p[r]=y;
	}
	i=0;
	edge[ek].x=l;
	edge[ek].y=r;
	edge[ek].v=z;
	while(a[l][i])i++;
	a[l][i]=ek;
	i=0;
	while(a[r][i])i++;
	a[r][i]=ek;
	ek++;
}
int st;
int ans[NMAX*NMAX];
int end;
int np;
int tmp;
void tr(int cp)
{
	int i=0;
	while(a[cp][i])
	{
		
		tmp=a[cp][i];
		if(edge[tmp].v)
		{
			np=cp==edge[tmp].x?edge[tmp].y:edge[tmp].x;
			int tp=edge[tmp].v;
			edge[tmp].v=0;
			tr(np);
			ans[end++]=tp;
		}
		i++;
	}
}
int check()
{
	int i,j;
	int sum;
	for(i=0;i<n;i++)
	{
		sum=0;
		j=0;
		while(a[i][j])
		{
			if(a[i][j])sum++;
			j++;
		}
		if(sum%2)
			return 0;
	}
	return 1;

}
void solve()
{
	int i=0;
	st=INF;
	end=0;
	int stk=-1;
	while(p[i])
	{
		if(st>p[i])
		{
			st=p[i];
			stk=i;
		}
		i++;
	}
	n=i;
	if(!check())
	{
		printf("Round trip does not exist.\n");
		return ;
	}
	tr(stk);
	
	
	for(i=0;i<end;i++)
	{
		printf("%d",ans[i]);
		if(i<end-1)
			printf(" ");
		else
			printf("\n");
	}
			
}
main()
{
#if _DEBUG 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int x,y,z;
	while(1)
	{
		ek=1;
		memset(p,0,sizeof(p));
		memset(a,0,sizeof(a));
		scanf("%d%d",&x,&y);
		if(!x)
			break;
		while(x)
		{
			scanf("%d",&z);
			add(x,y,z);
			scanf("%d%d",&x,&y);
		}
		solve();
	}
		
#if _DEBUG 
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}