1714.txt

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

#include <stdio.h>
#include <algorithm>

struct node
{
	int id;
	int order;
	node *l,*r,*f;
	int lv,rv,fv;
}tree[600];

node *leaf[600];

int n, k;
int e[600][3];
int v[600][3];
int d[600];

inline bool isleaf( node *s )
{
	return s->id < k;
}
		
int creat( node *r, node *f , int fv )
{
	int i, lo, ro;
	
	r -> f = f;
	r -> fv = fv;
	if( isleaf( r ) ) return r -> order;

	r -> lv = -1;

	for( i=0; i<3; i++ )
	{
		if( e[r->id][i] != f - tree )
		{
			if( r -> lv == -1 )
			{
				r->lv = v[r->id][i];
				r->l = tree+e[r->id][i];
				lo = creat( r->l, r, r->lv );
			}
			else
			{
				r->rv = v[r->id][i];
				r->r = tree+e[r->id][i];
				ro = creat( r->r, r, r->rv );
			}
		}
	}

	if( lo > ro )
	{
		std::swap( r->l, r->r );
		std::swap( r->lv, r->rv );
		r -> order = ro;
	}
	else r -> order = lo;
	
	return r -> order;
} 

void init()
{
	int i, j, a, b, va, h, t, g;
	
	scanf( "%d%d", &n, &k );

	for( i=0; i<n; i++ )
	d[i] = 0,tree[i].id = i;

	for( i=0; i< 3*n/2 ; i++ )
	{
		scanf( "%d%d%d", &a, &b, &va );
		a--,b--;
		e[a][ d[a] ] = b;
		v[a][ d[a] ] = va;
		d[a]++;
	
		e[b][ d[b] ] = a;
		v[b][ d[b] ] = va;
		d[b]++;
	}

	for( i=0; i<3; i++ )
	if( isleaf( tree+e[0][i] ) )
	{
		tree[0].l = tree+e[0][i];
		tree[0].lv = v[0][i];
		break;
	}

	h = e[0][i];

	for( j=1,t=0; h!=0; j++  )
	{
		tree[h].order = j;
		leaf[j] = tree+h;

		for( i=0; i<3; i++ )
		{
			if( e[h][i] == t )
			{
				tree[h].l = tree+e[h][i];
				tree[h].lv = v[h][i];
			}
			else if( isleaf( tree+e[h][i] ) )
			{
				tree[h].r = tree+e[h][i];
				tree[h].rv = v[h][i];
				g = e[h][i];
			}
		}

		t=h;
		h=g;
	}
	tree[0].r = tree+t;
	tree[0].rv = tree[t].rv;

	for( i=0; i<3; i++ )
	{
		if( e[0][i] != tree[0].l-tree && e[0][i] != tree[0].r-tree )
		{
			tree[0].f = e[0][i] + tree;
			tree[0].fv = v[0][i];
			break;
		}
	}

	creat( 	tree[0].f , tree, tree[0].fv );

}

int *output, m;

int calc_a_r( node *a, node *b, node *r );
int calc_r_b( node *a, node *b, node *r );


int calc_a_b( node *a, node *b, node *r )
{
	int ans = 0;

	if( a == b )
	{
		output[m++] = r->id;
		return 0;
	}

	ans +=	calc_a_r( a, leaf[r->r->order-1], r->l );
	output[m++] = r->id;
	ans += 	calc_r_b( leaf[r->r->order], b, r->r ) + r->lv + r->rv;

	return ans;
}

int calc_a_r( node *a, node *b, node *r )
{
	int ans;	

	if( a == b )
	{
		output[m++] = r->id;
		return 0;
	}

	ans =	calc_a_b( a, leaf[r->r->order-1], r->l ) +
	      	calc_a_r( leaf[r->r->order], b, r->r ) +
	      	r->rv + leaf[r->r->order]->lv;
	output[m++] = r->id;

	return ans;
}

int calc_r_b( node *a, node *b, node *r )
{
	
	output[m++] = r->id;

	if( a == b ) return 0;

	return	calc_r_b( a, leaf[r->r->order-1], r->l ) +
	      	calc_a_b( leaf[r->r->order], b, r->r ) +
	      	r->lv + leaf[r->r->order]->lv;
}

int answer[3][500];

int main()
{
	int i, ans1, ans2, ans3;

	init();

	m = 0; output = answer[0];
	ans1 = calc_a_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].rv;
	
	m = 0; output = answer[1];
	ans2 = calc_a_r( tree[0].l, tree[0].r, tree[0].f ) + tree[0].lv + tree[0].fv;
	
	m = 0; output = answer[2];
	ans3 = calc_r_b( tree[0].l, tree[0].r, tree[0].f ) + tree[0].rv + tree[0].fv;

	if( ans1 <= ans2 && ans1 <= ans3 )
		output = answer[0];
	else if( ans2 <= ans1 && ans2 <= ans3 )
		output = answer[1];

	printf( "%d", 1 );
	for( i=0; i<n-1; i++ )
		printf( " %d", output[i]+1 );
	printf( "\n" );

	return 0;
}