3041954_tle.cc

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

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define max 10100
#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, m, k, ans;
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, best;

bool cmp2(NODE a,NODE b)
{
	return a.w < b.w;
}

void init(int id)
{
	int i, j, tt;
	int tmp, minv, min;
	
	f = 1;r = 2;
	que[1] = best;
	memset(visited,0,sizeof(visited));
	visited[0] = 1;
	visited[best] = 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 > 0; i--)
	{
		if(i==best)
			continue;
		cnt[que[i]]++;
		cnt[info[que[i]].pa] += cnt[que[i]];
	}
	cnt[best]++;
	if(id)
		return ;
	tmp = -1;
	for(j = pos[1]; j < pos[2]; j++)
	{
		if(cnt[edge[j].v] > tmp)
		{
			tmp = cnt[edge[j].v];
		}
	}
	minv = 1;min = tmp;
	for(i = 2; i <= n; i++)
	{
		tmp = -1;
		for(j = pos[i]; j < pos[i+1]; j++)
		{
			if(edge[j].v==info[i].pa)
			{
				tt = n-cnt[i];
			}
			else
			{
				tt = cnt[edge[j].v];
			}
			if(tt > tmp)
			{
				tmp = tt;
			}
		}
		if(tmp < min)
		{
			min = tmp;
			minv = i;
		}
	}
	best  = minv;
}

void solve(int tot,int root)
{
	int i, 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;
	sort(&list1[1],&list1[1]+st1,cmp2);
	sort(&list2[1],&list2[1]+st2,cmp2);
	tmp = st2;
	for(i = 1; i <= st1; i++)
	{
		while(tmp>=1&&list1[i].w+list2[tmp].w+cost>k)	tmp--;
		if(tmp == 0)	break;
		ans += tmp;
	}
	solve(cnt[root],root);
	solve(cnt[minv],minv);
}

int main()
{
	int i, u, v, w;

	while(scanf("%d%d",&n,&k)==2)
	{
		if(n==0&&k==0)
		{
			break;
		}
		m = n - 1;
		for(i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			edge[i].id = edge[i+m].id = i;
			edge[i].u = edge[i+m].v = u;
			edge[i].v = edge[i+m].u = v;
			edge[i].w = edge[i+m].w = w;
		}
		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;
		best = 1;
		init(0);
		ans = 0;
		memset(checked,0,sizeof(checked));
		init(1);
		solve(cnt[best],best);
		printf("%d %d\n",best,ans);
	}
	return 0;
}