3806084_ac_688ms_10856k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define max 10001
#define hsize 10000001
#define inf 2100000000
using namespace std;

struct node
{
	int u, v;
	int w, id;
}edge[max*2];

bool cmp1(node a,node b)
{
	return a.u < b.u;
}

int n;
int checked[max], visited[max], pos[max], cnt[max], que[max];
int f, r;

struct Node
{
	int lenth;
	int pa, id;
}info[max];

struct NODE
{
	int v;
	int w;
}list1[max], list2[max];

int st1, st2;

void init()
{
	int i;
	
	f = 1;r = 2;
	que[1] = 1;
	memset(visited,0,sizeof(visited));
	visited[0] = 1;
	visited[1] = 1;
	while(f < r)
	{
		for(i = pos[que[f]]; i < pos[que[f]+1]; i++)
		{
			if(visited[edge[i].v]==visited[0])	continue;
			visited[edge[i].v] = visited[0];
			que[r] = edge[i].v;
			info[edge[i].v].pa = que[f];
			info[edge[i].v].lenth = edge[i].w;
			info[edge[i].v].id = edge[i].id;
			r++;
		}
		f++;
	}
	memset(cnt,0,sizeof(cnt));
	for(i = n; i > 1; i--)
	{
		cnt[que[i]]++;
		cnt[info[que[i]].pa] += cnt[que[i]];
	}
	cnt[1]++;
}

char h[hsize];
char hflag = 'A';

void solve(int tot,int root)
{
	int i, j, tmp, min;
	int cost, minv;

	min = inf;
	f = 1;r = 2;
	que[1] = root;
	visited[0]++;
	visited[root] = visited[0];
	while(f < r)
	{
		tmp = tot-cnt[que[f]]*2;
		if(tmp < 0)	tmp *= -1;
		if(tmp < min)	
		{
			min = tmp;
			minv = que[f];
		}
		for(i = pos[que[f]]; i < pos[que[f]+1]; i++)
		{
			if(visited[edge[i].v]==visited[0])	continue;
			if(checked[edge[i].id])	continue;
			visited[edge[i].v] = visited[0];
			que[r] = edge[i].v;
			r++;
		}
		f++;
	}
	if(minv==root)	return ;
	cost = info[minv].lenth;
	checked[info[minv].id] = 1;
	for(tmp = info[minv].pa; ; tmp = info[tmp].pa)
	{
		cnt[tmp] -= cnt[minv];
		if(tmp == root)	break;
	}
	f = 1;r = 2;
	list1[1].v = info[minv].pa;list1[1].w = 0;
	visited[0]++;
	visited[info[minv].pa] = visited[0];
	while(f < r)
	{
		for(i = pos[list1[f].v]; i < pos[list1[f].v+1]; i++)
		{
			if(visited[edge[i].v]==visited[0])	continue;
			if(checked[edge[i].id])	continue;
			visited[edge[i].v] = visited[0];
			list1[r].v = edge[i].v;
			list1[r].w = list1[f].w+edge[i].w;
			r++;
		}
		f++;
	}
	st1 = r-1;
	f = 1;r = 2;
	list2[1].v = minv;list2[1].w = 0;
	visited[0]++;
	visited[minv] = visited[0];
	while(f < r)
	{
		for(i = pos[list2[f].v]; i < pos[list2[f].v+1]; i++)
		{
			if(visited[edge[i].v]==visited[0])	continue;
			if(checked[edge[i].id])	continue;
			visited[edge[i].v] = visited[0];
			list2[r].v = edge[i].v;
			list2[r].w = list2[f].w + edge[i].w;
			r++;
		}
		f++;
	}
	st2 = r-1;
	tmp = st2;
	for(i = 1; i <= st1; i++)
	{
		for (j = 1; j <= st2; j++)
		{
			//printf("%d\n", list1[i].w + list2[j].w);
			h[list1[i].w + list2[j].w + cost] = hflag;
		}
	}
	solve(cnt[root],root);
	solve(cnt[minv],minv);
}

int main()
{
	int i, u, w, c, k, m;

	while (scanf("%d", &n) == 1 && n != 0)
	{
		hflag++;
		m = n - 1;
		c = 1;
		for (i = 1; i <= n; i++)
		{
			while (scanf("%d", &u) == 1 && u != 0)
			{
				scanf("%d", &w);
				edge[c].id = edge[c + m].id = c;
				edge[c].u = edge[c + m].v = i;
				edge[c].v = edge[c + m].u = u;
				edge[c].w = edge[c + m].w = w;
				c++;
			}
		}
		m <<= 1;
		sort(&edge[1],&edge[1]+m,cmp1);
		for(i = m; i > 0; i--)
		{
			pos[edge[i].u] = i;
		}
		pos[n+1] = m+1;
		init();
		memset(checked,0,sizeof(checked));
		solve(cnt[1], 1);
		while (scanf("%d", &k) == 1 && k != 0)
		{
			if (h[k] != hflag)
				puts("NAY");
			else
				puts("AYE");
		}
		puts(".");
	}
	return 0;
}