[HNOI2003] 消防局的设立

发表于 | 分类于 >
字数统计 : 615   |   阅读时长 ≈ 3 mins.

题目

链接

[HNOI2003]消防局的设立

题意简述

给出一棵节点数为 $n \ (n <= 1000)$ 的树，每条边长度为 $1$ 。

一次操作作用于一个节点，并将距此节点 $dist <= 2$ 的节点染色，求将整棵树染上颜色的最小次数。

思路

暴力

首先考虑暴力，也就是暴力枚举。
时间复杂度： $O(n^{2})$ 。
由于数据太水，暴力随便打吧。

贪心

一开始我是想到节点要尽可能向中间靠拢，染色少浪费，可是并不容易做到。
从上向下？没思路。（一开始没想到）
但从下向上就好想多了。
记录 $BFS$ 序，也就是深度。
从最底层找起，当它没被染色时，给它的爷爷（雾）染色 $(depth <= 2)$ ，这样能保证高效利用。
为什么不用 $DFS$ 记录呢？

  • 效率不及 $BFS$ 。
  • 记录深度还要排序，而 $BFS$ 记录只需要一个栈。
    时间复杂度： $O(n)$ （大概吧）。

树形DP

我太蒻了，并不会。。。。。

代码

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
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 2e3 + 10, kmax_int = 2147483647, kmod = 1e9+7;

#define pii std::pair<int, int>
#define ppiii std::pair<pii, int>
#define mp std::make_pair

int n;
pii e[kmax_num];
int head[kmax_num], cnt;

int f[kmax_num];

inline void AddEdge(REG int u, REG int v)	{
	e[++cnt] = mp(v, head[u]);
	head[u] = cnt;
	e[++cnt] = mp(u, head[v]);
	head[v] = cnt;
	return ;
}

std::queue<int> q;
std::stack<int> s;

inline void BFS()	{
	q.push(1), s.push(1);
	while(!q.empty())	{
		REG int u = q.front();		q.pop();
		for(REG int i = head[u]; i; i = e[i].second)
			if(e[i].first != f[u])	q.push(e[i].first), s.push(e[i].first);
	}
	return ;
}

bool vis[kmax_num];
std::queue<pii> mq;

inline void Mark(REG int u, REG int dep)	{
	mq.push(mp(u, 0));
	while(!mq.empty())	{
		REG pii u = mq.front();		mq.pop();
		for(REG int i = head[u.first]; i; i = e[i].second)	{
			vis[e[i].first] = 1;
			if(u.second < 1)	mq.push(mp(e[i].first, u.second + 1));
		}
	}
	return ;
}

int main() {
	std::cin >> n;
	FOR(i,1,n)	std::cin >> f[i + 1], AddEdge(f[i + 1], i + 1);

	BFS();
	REG int ans = 0;
	while(!s.empty())	{
		REG int u = s.top();		s.pop();
		if(!vis[u])
			vis[u] = true, Mark(f[f[u]], 0), ++ans;
	}
	printf("%d\n", ans);
	return 0;
}

杂项

  • 这里用了 $std::pair$ 实现，$std::pair$ 大法好！