poj 3107 Godfather 树的重心

缘起

继续学习树的重心. poj 3107 Godfather

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你n个顶点的无根树, 输出所有重心.

【输入】
第一行是n, 2 ≤ n ≤ 50 000, 树的顶点编号是1~n, 然后n-1行每行两个整数, 表示一条树边.

【输出】
输出所有的重心,按照顶点标号升序排序

【样例输入】
6
1 2
2 3
2 5
3 4
3 6

【样例输出】
2 3

【限制】
2s

此题比【1】还裸吧~ 直接打板子~ 注意, 本题只需要处理一组数据, 代码没怎么写注释, 详细注释参见【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 50005;
int n, head[maxn], cnt, top;
struct kk
{
	int pos,b; // kk是顶点i的标号, b是顶点i的平衡度
	bool operator <(kk &o)
	{
		return b==o.b?pos<o.pos:b<o.b; // 按平衡度升序排序, 如果平衡度一样的话, 则按照顶点标号升序排序
	}
}ans[maxn];
struct Arc
{
	int from, to, nxt;
}g[maxn<<1];

void addarc(int from, int to)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int dfs(int cur, int fa)
{
	int b = 0, ret = 1;
	for (int h = head[cur],to,son; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (to==fa)
		{
			continue;
		}
		son = dfs(to,cur);
		ret+=son;
		b = max(b, son);
	}
	b = max(b, n-ret);
	ans[top].pos = cur;
	ans[top].b = b;
	++top; // 不消说, top肯定最后和n相等
	return ret;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	int nn = n;
	while(--nn)
	{
		int a,b;
		scanf("%d%d", &a,&b);
		addarc(a,b);
		addarc(b,a);
	}
	dfs(1,0);
	sort(ans, ans+top); // 其实完全可以先找最小值然后O(n), 但是懒得去优化了,直接sort
	printf("%d",ans[0].pos);
	int i = 1;
	while(i<top && ans[i].b==ans[0].b)
	{
		printf(" %d", ans[i].pos);
		++i;
	}
	return 0;
}

ac情况

Status Accepted
Time 672ms
Memory 3028kB
Length 1222
Lang C++
Submitted 2019-11-06 11:35:20
Shared
RemoteRunId 21025860

参考

【1】https://yfsyfs.github.io/2019/11/06/poj-1655-Balancing-Act-%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83%E6%9D%BF%E9%A2%98/