题意
给出了一棵树，和一个初始的黑点（VOD服务器），所有边的边权均为1，你要求出最少还要染黑几个点，才能保证每一个白点到最近黑点之间的距离小于等于k。
思路
大概是贪心。
把给出的初始黑点当成树的根部，从根部dfs一次求出所有节点的深度，然后把深度最大的点（如果深度大于k）染黑，之后以这个点为中心dfs一次标记所有能覆盖的点。然后找第一个没有被覆盖的点，染黑，标记。。。直到所有点都被标记。
代码
|
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 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXV = 1005; const int MAXE = 2005; vector<int> leaf; int par[MAXV],dep[MAXV]; bool vis[MAXV]; int tot,head[MAXV],nxt[MAXE],end[MAXE]; int n,s,k; void init(){ leaf.clear(); tot = 2; for(int i = 1; i <= n; i++){ head[i] = 0; vis[i] = false; } } void addEdge(int from,int to){ end[tot] = to; nxt[tot] = head[from]; head[from] = tot++; } void input(){ scanf(" %d %d %d",&n,&s,&k); for(int i = 1; i< n; i++){ int a,b; scanf(" %d %d",&a,&b); addEdge(a,b); addEdge(b,a); } } void dfs(int cur,int _par,int cdp){ dep[cur] = cdp; par[cur] = _par; int cct = 0; for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(now != _par){ cct++; dfs(now,cur,cdp+1); } } if(!cct){ leaf.push_back(cur); } } bool cmp(int a, int b){ return dep[a] > dep[b]; } void mkr(int cur,int _par,int cdp){ if(cdp>=0){ vis[cur] = true; for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(now != _par){ mkr(now,cur,cdp-1); } } } } int solve(){ dfs(s,0,0); sort(leaf.begin(),leaf.end(),cmp); mkr(s,0,k); int ret = 0; for(int i = 0; i < leaf.size(); i++){ if(!vis[leaf[i]]){ ret++; int now = leaf[i]; for(int i = 1; i <= k; i++){ now = par[now]; } mkr(now,0,k); } } return ret; } int main(){ int caseCnt; scanf(" %d",&caseCnt); for(int d = 1; d <= caseCnt; d++){ init(); input(); printf("%d\n",solve()); } return 0; } |
