3390920_ac_594ms_12716k.cpp

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

#include <stdio.h>
#include <algorithm>
#define maxn 200000
#define min(a, b) a < b ? a : b

using namespace std;

int n, m;
struct node
{
	int u, v, w, f;

	bool operator < (const node & that)	const
	{
		return u < that.u;
	}
}edge[maxn * 2];

int flag;
int visited[maxn];
int father[maxn], id[maxn];
int pos[maxn];
int que[maxn];
int f, r;

void bfs()
{
	int i;

	f = 0;
	r = 1;
	que[0] = 0;
	father[0] = -1;
	visited[0] = flag;
	while (f < r)
	{
		for (i = pos[que[f]]; i < pos[que[f] + 1]; i++)
		{
			if (visited[edge[i].v] != flag)
			{
				visited[edge[i].v] = flag;
				que[r++] = edge[i].v;
				id[edge[i].v] = i;
				father[edge[i].v] = que[f];
			}
		}
		++f;
	}
}

int up[maxn], down[maxn], leaf[maxn];

void solve()
{
	int i, j, isleaf, tmp;

	for (i = r - 1; i >= 0; i--)
	{
		isleaf = 1;
		down[que[i]] = up[que[i]] = 0;
		for (j = pos[que[i]]; j < pos[que[i] + 1]; j++)
		{
			if (edge[j].v == father[que[i]])
			{
				continue;
			}
			isleaf = 0;
			if (leaf[edge[j].v])
			{
				down[que[i]] += edge[j].w;
				edge[j].f = edge[j].w;
			}
			else
			{
				down[que[i]] += (tmp = min(edge[j].w, down[edge[j].v]));
				edge[j].f = tmp;
			}
		}
		leaf[que[i]] = isleaf;
	}
	for (i = 1; i < r; i++)
	{
		if (father[que[i]] == 0 && pos[0] == pos[1] - 1)
			up[que[i]] = edge[0].w;
		else
			up[que[i]] += min(edge[id[que[i]]].w, down[father[que[i]]] + up[father[que[i]]] - edge[id[que[i]]].f);
	}
	int ans = -1;
	for (i = 0; i < n; i++)
	{
		tmp = up[i] + down[i];
		if (tmp > ans)
		{
			ans = tmp;
		}
	}
	printf("%d\n", ans);
}

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

	scanf("%d", &cas);
	flag = 1;
	while (cas-- > 0)
	{
		flag++;
		scanf("%d", &n);
		m = n - 1;
		for (i = 0; i < m; i++)
		{
			scanf("%d%d%d", &u, &v, &w);
			u--;v--;
			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, edge + m);
		for (i = m - 1; i >= 0; i--)
		{
			pos[edge[i].u] = i;
		}
		pos[n] = m;
		bfs();
		solve();
	}
	return 0;
}