abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S6916 【牧羊人】

发表于 更新于

Description

给你一棵有 $n$ 个点的树，有 $k$ 个点上有羊。你可以在一些点上放置牧羊人，牧羊人可以守护所有离它最近的羊。现在要让每只羊都被保护，求最少需要放置几个牧羊人，并构造出方案，给出其中一种即可。

Solution

有水平的贪心题。

考虑贪心选取当前没有被保护的羊中深度最大的那一只，如果有多只则随便选取一只即可。然后贪心找到最上面的能够保护它的位置，在它上面放置一个牧羊人，让后让它保护他能够保护的所有羊。如此不断循环，直到所有羊都被保护为止。

考虑证明为什么这样是对的。

因为这个位置一定在从它到根节点的简单路径上，又因为深度越小，能覆盖的点就越多，因此这种贪心选取的方法是对的。

考虑如果一个点 $u$，直接连接了一个点 $v$，若设 $\text{dis}_i$ 表示距离点 $i$ 最近的那只羊到点 $i$ 的距离（我们假设边权均为 1）。

那么如果 $\text{dis}_u = \text{dis}_v + 1$，那么在点 $u$ 放一个牧羊人等价于在点 $u$ 和点 $v$ 同时放一个牧羊人。

对于从点 $u$ 到根节点的简单路径上的所有的点 $v$，必定满足：

移项后可以得到：

如果我们设 $\text{up}_i$ 表示点 $i$ 向上深度最小的能够保护到点 $i$ 的点的编号，那么 $v = \text{up}_u$ 是能够使上式取得等号中深度最小的那一个点。

那么我们深搜一遍并在过程中就最大值就好了。

考虑怎么用牧羊人覆盖羊。

若点 $u$ 处有一个牧羊人，并且与之直接相连的并且当前没有被覆盖的点 $v$ 满足 $\text{dis}_u = \text{dis}_v + 1$，那么就递归下去覆盖点 $v$。由于每个点最多只会被覆盖一次，因此这部分的时间复杂度是 $O(n)$ 的。

Code

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <cstring>
#define maxN 500010
struct Edge{ int x, y, c, g; } b[maxN << 1];
int len = 0, n = 0, m = 0;
bool bj[maxN];
int ans[maxN], dep[maxN], dis[maxN], pos[maxN], up[maxN], dl[maxN], h[maxN], v[maxN];
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void bfs ()
{
	memset(dis, 127 / 3, sizeof(dis));
	int head = 1, tail = 1;
	for(int i = 1;i <= m; i++)
	{
		v[pos[i]] = 1;
		dis[pos[i]] = 0;
		dl[tail++] = pos[i];
	}
	while(head < tail)
	{
		int x = dl[head++];
		for(int i = h[x];i;i = b[i].g)
		{
			int y = b[i].y;
			if(dis[x] + 1 < dis[y])
			{
				dis[y] = dis[x] + 1;
				if(!v[y])
				{
					v[y] = 1;
					dl[tail++] = y;
				}
			}
		}
		v[x] = 0;
	}
}
void dfs (int x, int max, int last)
{
	int now = dis[x] + dep[x];
	if(now > max)
	{
		max = now;
		last = x;
	}
	up[x] = last;
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!dep[y])
		{
			dep[y] = dep[x] + 1;
			dfs(y, max, last);
		}
	}
}
void px (int l, int r)
{
	int x = l, y = r, mid = dep[pos[(l + r) >> 1]];
	while(x <= y)
	{
		while(dep[pos[x]] > mid)
		{
			x++;
		}
		while(dep[pos[y]] < mid)
		{
			y--;
		}
		if(x <= y)
		{
			int t = pos[x];
			pos[x] = pos[y];
			pos[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
void cover (int x)
{
	bj[x] = true;
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(!bj[y] && dis[x] == dis[y] + 1)
		{
			cover(y);
		}
	}
}
void work ()
{
	for(int i = 1;i <= m; i++)
	{
		if(!bj[pos[i]])
		{
			cover(up[pos[i]]);
			ans[++ans[0]] = up[pos[i]];
		}
	}
}
int main ()
{
	scanf("%d %d", &n, &m);
	for(int i = 1;i < n; i++)
	{
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		ins(x, y), ins(y, x);
	}
	for(int i = 1;i <= m; i++)
	{
		scanf("%d", &pos[i]);
	}
	bfs();
	int root = 1;
	dep[root] = 1;
	dfs(root, 0, 0);
	px(1, m);
	work();
	printf("%d\n", ans[0]);
	for(int i = 1;i <= ans[0]; i++)
	{
		printf("%d ", ans[i]);
	}
	return 0;
}