Uva(1267)(Network)

链接:https://vjudge.net/problem/UVA-1267
思路:由于各个客户端都可以看做树的根节点，我们考虑从根节点开始向前搜索，当距离大于k且没遇到原来VOD的时候即要安装一个服务器。那遇到有多条路时怎么决定往哪边走呢(即决定服务器位置放哪里，从而保证是最优解)，不难想到，如果我们从深度最深的根节点开始一直向上走，然后当刚好大于k距离时安装一台服务器，这样的解一定是最优的，为了区分服务器和VOD，我们可以在安装服务器后马上进行一次dfs，对能达到的根节点进行标记。
那么如何进行根节点深度的排序呢，我们可以进行一次bfs，然后遇到根节点就把它放入vector中，这样再倒着遍历一遍vector就是按照根节点深度从大到小的顺序进行遍历，从而确保了最优解，然后如果需要按照服务器就进行一次遍历，将能达到的其他根节点进行标记为已经覆盖。
代码:

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int t,n,p,k,a,b,res = 0;;

int visss[1001];//dfs中判重
int viss[1001];//bfs中判重
int pre[1001];
int cover[1001];
vector<int> G[1001],nodes; //G记录边信息，nodes记录根节点信息

//bfs确定深度，从而按深度放入nodes中
void bfs(int w){
    queue<int> qq;
    qq.push(w);
    viss[w] = 1;
    pre[w] = -1;
while(!qq.empty()){
    int e = qq.front();
    qq.pop();
    for(int i=0;i<G[e].size();i++){
        int v = G[e][i];
        if(viss[v])continue;
        pre[v] = e;
        viss[v] = 1;
        if(G[v].size()==1)nodes.push_back(v);
        else{
        qq.push(v);
        }
    }
}
}

//安装新服务器后对其他能覆盖的根节点的扫描
void dfs(int w,int dd){
    if(dd>k)return;
    if(G[w].size()==1)cover[w] = 1;
for(int i=0;i<G[w].size();i++){
    if(!visss[G[w][i]]){
        visss[G[w][i]] = 1;
    //  printf("%d\n",G[w][i]);
        dfs(G[w][i],dd+1);
    }
    else continue;
}
}

void solve(){
    for(int i=nodes.size()-1;i>=0;--i){//按根节点深度从大到小进行排序遍历
        if(cover[nodes[i]]==1)continue;
        int v = nodes[i];
    for(int l=0;l<k;++l){
        v = pre[v];
        if(v==p){
            cover[nodes[i]] = 1;
            break;
        }
    }
    if(cover[nodes[i]]==0){
        memset(visss,0,sizeof(visss));
        visss[v] = 1;
        res++;
    //  printf("%d %d\n",v,nodes[i]);
        dfs(v,0);
    }
    }
}


int main(){
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--){
        for(int i=0;i<n;i++)G[i].clear();
        nodes.clear();
        int times = 0;
        res = 0;
        memset(viss,0,sizeof(viss));
        memset(pre,0,sizeof(pre));
        memset(cover,0,sizeof(cover));
        scanf("%d%d%d",&n,&p,&k);
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
    bfs(p);
    solve();
    printf("%d\n",res);
    }
    return 0;
}