首页 > 代码库 > LA 3902

LA 3902

  之前对树的处理一般是从根节点开始递归处理。今天学习了一种新方法,根据层的深浅处理。即,1、首先得到每个节点的深度 2、然后从最底层开始处理。(貌似是宽搜的逆处理)

      题意:给出一个棵树,从根节点向叶节点发信息。如果距离大于k就无法发送信息(节点之间的距离为1)。 为了能够给所有叶节点传送到信息,需要在树立增加一些服务器,这些服务器也能发送信息,如果一个叶节点离最近的服务器距离不超过k,那么也认为这个叶节点是接收到信息的。求最少需要增加多少个服务器可以让所有的叶节点都能收到信息。

      思路:开始的时候就认为是一个树形dp,想了一会儿想出了办法,但是处理比较复杂。后来发现了一个方便,处理比较好一点。

      可以发现深度不大于k的叶节点不需要管。 对于深度大于k的叶节点,我们优先处理较深节点。对于当前未处理的节点,我们优先处理最深的节点,将服务器放到最深节点的前k层祖先的位置不会让最优结果变坏。 我们放一个服务器后需要将距离服务器距离不大于k的叶节点全部染色(即处理)。

      AC代码:

      

#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <algorithm>using namespace std;const int N = 1050;int n, k, s;vector<int>edge[N];vector <int> g[N];bool covered[N];int f[N];void init(){    scanf("%d", &n);    scanf("%d%d", &s, &k);    int u, v;    for(int i=0; i<=n; i++)    {        edge[i].clear();        g[i].clear();    }    for(int i=1; i<n; i++)    {        scanf("%d%d", &u, &v);        edge[u].push_back(v);        edge[v].push_back(u);    }}void dfs(int u, int pre, int d){    f[u] = pre;    int sz = edge[u].size(), v;    if(sz == 1 && d > k)    {        g[d].push_back(u);    }    for(int i=0; i<sz; i++)    {        v = edge[u][i];        if(v == pre) continue;        dfs(v, u, d+1);    }}void dfs2(int u, int pre, int d){    covered[u] = true;    int v = 0;    for(int i=0; i<edge[u].size(); i++)    {        v = edge[u][i];        if(v == pre) continue;        if(d < k)        {            dfs2(v, u, d+1);        }    }}void solve(){    dfs(s, -1, 0);    memset(covered, 0, sizeof(covered));    int ans = 0, u, v;    for(int i=n-1; i>k; i--)    {        for(int j=0; j<g[i].size(); j++)        {            u = g[i][j];            if(covered[u]) continue;            v = u;            for(int j=0; j<k; j++) v = f[v];            dfs2(v, -1, 0);            ans++;        }    }    printf("%d\n", ans);}int main(){    int t;    scanf("%d", &t);    while(t--)    {        init();        solve();    }    return 0;}
View Code

 

LA 3902