贪心--ACM-ICPC Live Archive3902Networkt

题目翻译（有篡改题目背景） description 绝境长城以北是一片凶险之地，但是有守夜人的游骑兵在外巡视保证长城以内的安全，就这样过了很久很久。直到了第六季，守夜人的总司令john snow被自己的兄弟杀死，虽然被stannis的火焰女祭司用魔法复活，但是他对守夜人兄弟非常失望，准备回老家winter hell。总司令走了，守夜人军心涣散，特别是在长城以北的游骑兵变得非常害怕。长城以外的地形成一个树状结构，总共有n个节点(3<=n<=1000)，其中每条边的长度均为1，游骑兵们就守在叶子节点处。由于游骑兵变得非常害怕，看到异鬼就跑并且还不一定跑得掉，大家决定在树上的某些节点修建一些堡垒使得white walker来临时所有的游骑兵都能安全的跑回堡垒而不是被抓住。因为white walker的死骑跑得非常快，而游骑兵的马跑得很慢，所以每一个游骑兵距离最近的堡垒的距离有一定的限制（即距离不能超过k，1<=k<=n），不然游骑兵就会被异鬼抓住并成为死人军团中的一员。(因为异鬼非常厉害，可以同时追杀每一个游骑兵，所以要求每一个游骑兵都能安全逃离。)然而除了可以在堡垒避难，当然还可以跑到长城的隧道口（隧道口所在节点的编号为s，这是现成的不需要修建，1<=s<=n）穿过长城到达黑城堡（castle black），当然这里是最安全的（即在隧道口和堡垒处都是安全的）。 请问最少修建多少个堡垒可以保证每一个游骑兵都是安全的？ input 第一个数t为数据的组数。对于每一组数据，前三个数分别为n，s，k。后面n-1行，每行2个数a，b。即a，b之间有一条边。 output 输出最少的堡垒数。（每组输出之间要换行） sample input 2 14 12 2 1 2 2 3 3 4 4 5 5 6 7 5 8 5 4 9 10 3 2 12 12 14 13 14 14 11 14 3 4 1 2 2 3 3 4 4 5 5 6 7 5 8 5 4 9 10 3 2 12 12 14 13 14 14 11 sample output 1 0 分析：由题意，离隧道口距离小于等于k的游骑兵就可以不管了，剩下的，无根树转有根树，现成的树根：s。   从深度最深的叶子节点开始。对于这样一个节点，k层及以下的祖先修一个堡垒就可以保证这一个游骑兵的安   全，当然，刚刚的k层祖先是最划算的（想一想为什么？）。有了这样一个原则就可以开始了。输入后先深搜   一次建树并预处理。后面每确定一个堡垒的位置就从这里深搜一次，记录下由这个堡垒覆盖安全的节点。   废话不多说，看代码。 #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstdlib> #include<cstring> using namespace std; const int maxn=1005; vector<int> link[maxn],node[maxn]; int father[maxn]; bool cover[maxn]; int n,s,k; void clear(){ int i,j; for(i=0;i<=maxn;i++){ link[i].clear(); node[i].clear(); memset(father,0,sizeof(father)); memset(cover,0,sizeof(cover)); } } void dfs(int u,int fa,int depth){ father[u]=fa; if(link[u].size()==1&&depth>k)node[depth].push_back(u); int i,j; for(i=0;i<link[u].size();i++){ if(link[u][i]!=fa)dfs(link[u][i],u,depth+1); } } void dfs2(int u,int fa,int depth){ cover[u]=true; if(depth==k)return; int i,j; for(i=0;i<link[u].size();i++){ int v=link[u][i]; if(v!=fa)dfs2(v,u,depth+1); } } int work(){ int i,j,d,tot=0; for(d=n-1;d>k;d--){ for(i=0;i<node[d].size();i++){ int u=node[d][i]; if(cover[u])continue; int fa=u; for(j=1;j<=k;j++)fa=father[fa]; dfs2(fa,-1,0); tot++; } } return tot; } int main(){ int t; cin>>t; while(t--){ clear(); scanf("%d%d%d",&n,&s,&k); int i,j; for(i=1;i<n;i++){ int a,b; scanf("%d%d",&a,&b); link[a].push_back(b); link[b].push_back(a); } dfs(s,-1,0); printf("%d\n",work()); } }