上一篇博客题目的普遍情况

这里跟前面那道题有点不同的地方是它的半径变得任意可变，并且给了一个初始的节点已经覆盖，并且最终的目的是让所有的叶子都覆盖。

做法跟上道题是类似的。

无根树还是变成有根树好，既然直接给了我们一个特殊点，那就直接拿它做根。

首先先dfs一下，判断哪些点是叶子，顺便统计出dep数组。

既然根已经添加，直接先半径为\(k\)地覆盖一下。把一些初始化就覆盖好的叶子忽略掉。

然后就是一样的弄一个堆，按照深度大小来排序，深度大的叶子先出队。

这个叶子直接取它的\(k\)级父亲，然后就拿它来覆盖就可以了。直到所有叶子都覆盖完。

代码：

#include<cstdio>#include<cstring>#include<queue>const int maxn = 1005;struct Edges{ ???int next, to;} e[maxn << 1];int head[maxn], tot;int dep[maxn], fa[maxn];bool vis[maxn];bool leaf[maxn];int n, s, k;struct cmp{ ???bool operator () (const int &a, const int &b) const ???{ ???????return dep[a] < dep[b]; ???}};void link(int u, int v){ ???e[++tot] = (Edges){head[u], v}; ???head[u] = tot;}void dfs(int u, int f){ ???dep[u] = dep[f] + 1; fa[u] = f; ???int cnt = 0; ???for(int i = head[u]; i; i = e[i].next) ???{ ???????cnt++; ???????int v = e[i].to; ???????if(v == f) continue; ???????dfs(v, u); ???} ???if(cnt == 1) leaf[u] = true;}void dfs2(int u, int f, int d){ ???vis[u] = true; ???if(d == k) return; ???for(int i = head[u]; i; i = e[i].next) ???{ ???????int v = e[i].to; ???????if(v == f) continue; ???????dfs2(v, u, d + 1); ???}}int main(){ ???int T; scanf("%d", &T); ???while(T--) ???{ ???????memset(head, 0, sizeof head); tot = 0; ???????scanf("%d%d%d", &n, &s, &k); ???????for(int i = 1; i < n; i++) ???????{ ???????????int u, v; scanf("%d%d", &u, &v); ???????????link(u, v); link(v, u); ???????} ???????memset(dep, 0, sizeof dep); ???????memset(fa, 0, sizeof fa); ???????dfs(s, 0); ???????memset(vis, false, sizeof vis); ???????dfs2(s, 0, 0); ???????std::priority_queue<int, std::vector<int>, cmp> heap; ???????for(int i = 1; i <= n; i++) ???????{ ???????????if(leaf[i] && !vis[i]) heap.push(i); ???????} ???????int ans = 0; ???????while(!heap.empty()) ???????{ ???????????int x; ???????????while(!heap.empty() && vis[x = heap.top()]) heap.pop(); ???????????if(heap.empty()) break; ???????????int v = x; ???????????for(int i = 1; i <= k; i++) v = fa[v]; ???????????dfs2(v, 0, 0); ???????????ans++; ???????} ???????printf("%d\n", ans); ???} ???return 0;}

UVALive - 3902 Network

原文地址：https://www.cnblogs.com/Garen-Wang/p/9882816.html