题目

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1903

题意

一棵树,根上有VOD站,要求任意叶节点到VOD站的距离不超过k,问最少建新VOD站数。

思路

1. 令vod[i]为节点i到VOD站的最短距离,  注意,这是在以i为根的树上有VOD站的情况下,如果没有,vod[i]就设为非法。

依据树形DP的思路,如果在该节点(非叶节点)建站,vod[i]=0,否则 vod[i] = min(vod[child] + 1) for child in i.children.(此时注意不要统计没有VOD的子树的非法值)

2. 令urge[i]为以i为根的树中有叶节点还没被满足的情况下,该节点能忍受VOD站在此树外的最远距离。注意如果所有叶节点都被满足了,urge[i]就设为非法。

对于叶节点, urge[i] = k,对于非叶节点,urge[i] = min(urge[child] + 1] for child in i.children),(此时注意不要统计已经被满足的非法值)

3. 如何判断这棵树的孩子们之间有没有相互满足?明显,如果urge[i]和vod[i]都存在,且urge[i] <= vod[i],则说明有兄弟相互满足的情况。

4. 如果孩子们之间无法相互满足?如果urge[i] > 0,说明不紧迫,交给父亲树去办。如果urge[i] = 0,说明需要建新站。

感想

1. 注意边是无向边,因此边数是点数2倍!

代码

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 2e3 + ;
const int inf = 0x3ffffff;
int n, k, s;
int vod[MAXN];
int urge[MAXN];
int first[MAXN];
int to[MAXN];
int nxt[MAXN];
int edgeNum; void addEdge(int f, int t) {
nxt[edgeNum] = first[f];
to[edgeNum] = t;
first[f] = edgeNum++;
} int dfs(int root, int fa) {
if (nxt[first[root]] == -) {
urge[root] = k;
vod[root] = inf;
return ;
}
int ans = ;
vod[root] = inf;
urge[root] = inf;
for (int p = first[root]; p != -; p = nxt[p]) {
int t = to[p];
if (t == fa)continue;
ans += dfs(t, root);
if (vod[t] != inf) {
vod[root] = min(vod[t] + , vod[root]);
}
if (urge[t] != inf) {
urge[root] = min(urge[t] - , urge[root]);
}
}
if (urge[root] != inf) {
if (vod[root] != inf && vod[root] <= urge[root]) {
urge[root] = inf;//satisfied
}
else if (urge[root] == && root != s) {
ans ++;
vod[root] = ;//set up a new one;
urge[root] = inf;//satisfied
}
}
return ans;
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
scanf("%d", &T);
for (int ti = ; ti <= T; ti++) {
memset(first, -, sizeof first);
edgeNum = ;
scanf("%d%d%d", &n, &s, &k);
for (int i = ; i < n; i++) {
int f, t;
scanf("%d%d", &f, &t);
addEdge(f, t);
addEdge(t, f);
}
int ans = dfs(s, -);
printf("%d\n", ans); } return ;
}
05-06 23:02