3041879_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;

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

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]++;
}

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;
		init();
		ans = 0;
		memset(checked,0,sizeof(checked));
		solve(cnt[1],1);
		printf("%d\n",ans);
	}
	return 0;
}