牛客NOIP暑期七天营-普及组6-C-Bunny的修路工程
Bunny的修路工程
https://ac.nowcoder.com/acm/contest/930/C
题目大意:n个点n-1条边的一棵树,有m个点是超市;现在每个点到超市的最短距离都不超过D,至多删除多少条边,还能够保证每个点到超市的最短距离都不超过D?
预处理:超市点的数量是x,非超市点是y,x+y = n。
1、对于不是超市的点,都需要1条边来连向超市,所以至少需要y条边,至多删除n-1 - y条边。
2、要想删边后每个点到超市的距离不超过D,可以用y条边就够了。
超市不需要用边;非超市点,必有一条路连向超市,选距离最短的。不需要管怎么找到这条路,因为我们只需要知道是否可行就够。
#include <bits/stdc++.h> #define N 1000005 using namespace std; int n, m, i, j, k, ans, f[N]; int main(){ scanf("%d%d%*d", &n, &m); for(i=1; i<=m; i++){ scanf("%d", &k); if(++f[k] == 1) ans++; } printf("%d\n", (n-1)-(n-ans)); return 0; }