本文主要是介绍EOJ Monthly 2020.9 B. 健康监测计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
B. 健康监测计划
单点时限: 2.0 sec
内存限制: 256 MB
QQ 小方接到了来自学校防控疫情指挥部的任务，协助指挥部部署校园内的健康监测站。
华东师范大学共有 n 栋楼房，编号为 1,2,…,n，并有 n−1 条双向联通的道路连接这些楼房，使得任意两栋楼房之间有且仅有一条简单路径（一条简单路径是指，从一栋大楼出发，不经过重复大楼，并在另一栋大楼结束的路径）。学校为了贯彻落实常态化疫情防控政策，决定选择一些楼房，在其中各设置一个健康监测点，实时监测路过的同学的健康状况。
虽然自动化检查仪器已经在全校普及，但是监测的过程依然不可避免地会影响学生的出入便捷性。所以学校需要精心安排监测点的位置，使得监测点数量尽可能多，而且尽量不对师生们造成太大的麻烦。具体而言，对于任意一条从某一栋楼开始在另一栋楼结束的简单路径，你需要保证路径上的监测点的数量不超过 k（包括起点和终点上的监测点），并在此前提下最大化监测点的数量。
输入格式
第一个输入两个整数 n 和 k（2≤n≤106，0≤k≤n），表示华师大楼房的个数以及任意一条简单路径上的监测点数目上限。
接下来 n−1 行，每行输入两个不同的正整数 u,v（1≤u,v≤n），表示有一条直接连接 u 号楼房和 v 号楼房的双向道路。
输出格式
一行，一个整数，表示最多能放置多少个健康监测站。
样例
input
10 1
1 4
1 2
2 5
2 3
2 7
2 8
5 6
6 10
8 9
output
1
input
8 2
5 1
7 1
2 1
4 7
6 7
8 6
3 4
output
4
思路：考虑k=1的时候，答案是1，k=2的时候，答案是所有叶子结点的个数，k=3的时候，答案是所有叶子结点的个数+1，k=4的时候，答案是所有叶子结点的个数+去掉这些叶子结点之后的叶子结点个数，不难推测出k是偶数的时候，答案是所有深度为小于等于k/2的结点个数总和，k是奇数的时候,答案是深度为小于等于k/2的结点个数+1。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;const int maxn = 2e6 + 100;
struct node{int to, next;
}edge[2 * maxn];int n, k;
int cnt = 0;
int head[2 * maxn];
int indegree[maxn];
int cntt[maxn];
int ans[maxn];void add(int u, int v)
{edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}queue<int>q;
void bfs()
{while(!q.empty()){int u = q.front();q.pop();//找到与u相连的边for(int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;cntt[v] = cntt[u] + 1;//入度为2的时候，减去叶子结点，只剩下一个结点,if(--indegree[v]==1){ans[cntt[v]]++;q.push(v);}}}
}void input()
{scanf("%d%d", &n, &k);memset(head, -1, sizeof(head));for(int i = 1; i < n; i++){int u, v;scanf("%d%d", &u, &v);indegree[u]++, indegree[v]++;add(u, v), add(v, u);}
}int main()
{input();for(int i = 1; i <= n; i++){//找到所有入度为1的结点（叶子节点）if(indegree[i] == 1){cntt[i] = 1;ans[1]++;q.push(i);}}bfs();int tot = 0;for(int i = 1; i <= k / 2; i++){tot += ans[i];}if(k & 1)tot++;tot = min(tot, n);printf("%d\n", tot);return 0;
}
这篇关于EOJ Monthly 2020.9 B. 健康监测计划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
