题解 P3942 【将军令】

YWY_wys · 2018-04-29 09:52:12 · 题解

贪心

做这个题之前建议先做做这个题

题意：

给一颗树，每次选一个点，覆盖该点及其周围与其距离不超过k的节点，求最少需要选多少个点。

题解：

考虑贪心，我们每次覆盖尽量多的节点，怎么覆盖呢。我们每次从深度最深的节点开始，选它的k级父亲覆盖。这样去贪心是正确的。它满足贪心的性质。1.问题具有子结构。2.这样决策无后效性。3.在此前提下（无后效性），没有比这样选更优的选法。

一些细节:当树根决定后，每次这样覆盖对节点深度无影响。树根可以随便选。

具体操作：开个优先队列把所有节点都压进去，每次弹出深度最深的节点，判断是否覆盖过，如果没覆盖过，找其k级父亲并覆盖其周围距离不超过k的所有节点。

code：

#include<cstdio>
#include<queue>

using namespace std;

const int maxn=100005;
const int maxm=200005;

struct e{
    int u,v,nxt;
} edge[maxm];

struct node{
    int u,d;
    node() {}
    node(int u_,int d_) {u=u_;d=d_;}
    bool operator < (const node &a) const {return d<a.d;}
    bool operator > (const node &a) const {return d>a.d;}
};

int n,k,t,cnt,ans;
int head[maxn],dep[maxn],fa[maxn];
bool vis[maxn];
priority_queue<node> q;

void adde(int u,int v) {
    edge[++cnt]=(e) {u,v,head[u]};
    head[u]=cnt;
}

void dfs1(int u) {
    int v;
    for(int i=head[u];i;i=edge[i].nxt) {
        v=edge[i].v;
        if(!dep[v]) {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
        }
    }
}

int find(int x) {
    int stp=1;
    while(stp<=k) {
        stp++;
        x=fa[x];
    }
    return x;
}

void dfs2(int u,int rt,int stp) {
    int v;
    vis[u]=true;
    if(stp==k) return ;
    for(int i=head[u];i;i=edge[i].nxt) {
        v=edge[i].v;
        if(v!=rt) dfs2(v,u,stp+1);
    }
}

int main() {
    int x,y,u,v;
    scanf("%d%d%d",&n,&k,&t);
    for(int i=1;i<n;i++) {
        scanf("%d%d",&x,&y);
        adde(x,y);adde(y,x);
    }
    dep[1]=1;fa[1]=1;dfs1(1);
    for(int i=1;i<=n;i++) q.push(node(i,dep[i]));
    while(q.size()) {
        u=q.top().u;q.pop();
        if(vis[u]) continue;
        ans++;
        v=find(u);
        dfs2(v,v,0);
    }
    printf("%d",ans);
}