uva 1267 Network

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

题意:给一个无根树,一开始在S点放一个服务器器(其实就是有根树了……),S的作用范围是D,目的是覆盖所有的叶子,但是可以有些叶子到S的距离超过D,所以还需要在一些非叶子节点添加服务器,每个服务器的作用范围一样是D,问要覆盖掉所有叶子最少需要另外添加的服务器数(即不包括原来的S)

这题也不太算是树dp吧,就分析一下然后搜一下就行了

  1. 以S为根,dfs整个树,算出每个点的深度,当然算出了所有叶子的深度
  2. 找到最深的那个叶子,从这个叶子往上走d层(并且不能超过S),找到一个点rt,选这个点做服务器,一定能覆盖到最深的叶子,并且选它一定是最优的,以这个点为中心,做一个bfs,在rt周围距离为d以内的点全部搜遍,是叶子的话就标记被覆盖了。
  3. 对于已经被标记的叶子可以跳过了,没有标记的叶子重新第2步。直到所有叶子都被覆盖
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1010
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,S,D,fa[N],dep[N];
vector<int>e[N];
vector<pii>Leaf;
bool color[N],leaf[N];

bool cmp(pii x , pii y){
return x.second > y.second;
}

void dfs(int u,int par,int d){
fa[u] = par; dep[u] = d;
leaf[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa[u]) continue;
leaf[u] = false;
dfs(v,u,d+1);
}
if(leaf[u]) Leaf.pb(mp(u,d));
}

int find(int u){
int d = D;
while(u != S && d){
u = fa[u]; d--;
}
return u;
}

void bfs(int rt){
bool vis[N];
queue<pii>que;
cl(vis,false);
while(!que.empty()) que.pop();
que.push(mp(rt,0));
while(!que.empty()){
pii x = que.front(); que.pop();
int u = x.first , d = x.second;
if(leaf[u]) color[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(vis[v] || d+1 > D) continue;
que.push(mp(v,d+1));
vis[v] = true;
}
}
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&S,&D);
for(int i = 0; i <= n; i++)
e[i].clear();
Leaf.clear();
cl(fa,-1); cl(dep,-1); cl(color,false);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
dfs(S,-1,0);
sort(Leaf.begin(),Leaf.end(),cmp);
//for(int i = 0; i < Leaf.size(); i++)
// printf("%d --- %d\n",Leaf[i].first,Leaf[i].second);
int cnt = 0;
for(int i = 0; i < Leaf.size(); i++){
int x = Leaf[i].first;
if(color[x]) continue;
int rt = find(x);
if(rt != S) cnt++;
bfs(rt);
}
printf("%d\n",cnt);
}
return 0;
}