P3523 [POI2011]DYN-Dynamite

2018-03-27 18:53:15


这道题乍一看非常毒瘤(其实我连题都没看懂)

看到最大值最小,可以想到二分答案

我们直接二分出题目所求的“关键节点到这些点中距离的最小值的最大值”

然后题意转化成为:已知一个点可以覆盖的范围,判断能否用不超过m个点覆盖整棵树

那么如何check二分的答案呢?

可以用贪心解决(虽然我也是看了题解)

从1号节点开始dfs,直到当前节点k与关键节点的距离达到mid,就把k选中

贪心的正确性是比较显然的:

如果在k的子树中选择了节点,则其向上能覆盖的范围一定不会超过k的覆盖范围

楼下Kelin大佬讲得非常详细(太强了)

丑陋的代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=3e5+5;
struct edge
{
    int to,nxt;
}edge[N<<1];
int n,m,num,t,tot,f[N],fa[N],cnt[N],head[N];
bool ex[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    head[from]=num;
}
void dfs(int k)//已知覆盖范围,用最少的点覆盖整棵树(从下向上贪心,必须选才选) 
{
    int tmp1=ex[k]?0:-1e7,tmp2=-1e7;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa[k]) continue;
        fa[v]=k; dfs(v);
        if (cnt[v]==1) tmp1=max(tmp1,f[v]+1);
        if (cnt[v]==2) tmp2=max(tmp2,f[v]-1);
    }
    if (tmp1>tmp2)
      if (tmp1==t) ++tot,cnt[k]=2,f[k]=t;
      else cnt[k]=1,f[k]=tmp1;
    else cnt[k]=2,f[k]=tmp2;
}
inline bool check(int k)//即一个选择点能覆盖的范围 
{
    t=k; tot=0; dfs(1);
    if (f[1]>=0&&cnt[1]==1) ++tot;
    return tot<=m;
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;ex[i++]=read());
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    int l=0,r=n,ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;//关键点与选择点之间距离最小值的最大值 
        if (check(mid))
        {
            ans=mid; r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}