洛谷1084 疫情控制

题解 算法-二分/三分 算法-贪心 算法-倍增 省选/NOI-
题目链接 编辑文章

题意

一棵 $n(\le 50000)$ 个点的树,有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守,军队可以同时移动,每小时移动 $1$ 单位长度。问至少要多久才能满足条件,无解输出 -1(没有)

题解

答案显然满足单调性,所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)

如果军队 $i$ 在根节点到叶子节点 $j$ 的路径上,就称 $i$ 管辖了 $j$ 。可以发现深度越小,管辖的节点越多,所以可以先把节点尽量往上提。(2)

令根节点的子节点组成的集合为 $S$ 。如果某支军队到不了根,就让它停下并驻守在最远能到达的位置;如果能到根,那么它就可能可以跨过根节点去管辖其它节点,不过先让它停在能到达的 $S$ 上,并记录它所在的位置和还能走的距离为 $u$ 。然后将这些军队按照还能走的距离排序。(3)

然后以各个 $S$ 为起点进行搜索,得到以它们为根的子树的叶节点是否全部被管辖,并记录为 $res[i]$ 。(4)

然后按排序后的顺序遍历 $u$ ,如果存在某支军队 $i$ 所在的节点还没被覆盖,并且它不能走到根节点并回到这里,就让它驻守在这里,并从 $u$ 中把它删去。(5)

因为它不能再回到这里,所以它跨过根节点后也只能去管辖一个离根节点更近的 $S$ ,同时需要有一个 $i'$ 来管辖这里。这个 $i'$ 剩下的距离就一定 $> i$ ,所以不如把 $i$ 留在这里,让 $i'$ 去覆盖其它节点。

这一步后把子树还是没被完全管辖的 $S$ 记录进 $v$ ,并按照它到根的距离排序。(6)

然后遍历所有的 $u$ 和 $v$ ,按贪心的思想依次管辖,如果所有的 $v$ 都被管辖那么就满足条件。(7)

可以发现需要预处理出倍增的祖先节点数组 $fa[i][j]$ 和与祖先节点之间的距离 $dis[i][j]$ 。(8)

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<ll,int>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=50005;
struct Edge {
    int next,to,w;
} edge[N<<1];
ll dis[N][17];
bool vis[N],res[N],del[N];
int cnt,head[N],n,m,a,b,c,s[N],fa[N][17];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int f,int di) //(8):倍增预处理
{
    fa[x][0]=f;
    dis[x][0]=di;
    for (int i=1;i<=16;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        dis[x][i]=dis[x][i-1]+dis[fa[x][i-1]][i-1];
    }
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x,edge[i].w);
    }
}

bool dfs2(int x,int f)
{
    if (vis[x]) return 1; //有军队驻守
    bool flag=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        flag=1; //不是叶子节点
        if (!dfs2(y,x)) return 0;
    }
    return flag; //如果都访问到叶子节点了那就返回false
}

inline bool check(ll mid)
{
    vector <pii> u,v;
    memset(vis,0,sizeof(vis));
    memset(del,0,sizeof(del));
    for (int i=1;i<=m;i++)
    {
        int x=s[i]; ll dsum=0;
        for (int j=16;~j;j--) //(2):尽量往上提
        {
            if (fa[x][j]<=1 || dsum+dis[x][j]>mid) continue;
            dsum+=dis[x][j];
            x=fa[x][j]; //注意这两句话的顺序
        }
        if (fa[x][0]==1 && dsum+dis[x][0]<=mid) u.push_back(mp(mid-dsum-dis[x][0],x)); //(3):记录能到根的节点
        else vis[x]=1; //(3):不能到根就驻守在这
    }
    sort(u.begin(),u.end()); //(3):按还能走的距离排序
    for (int i=head[1];i;i=edge[i].next) //(4):得到各个S的子树是否被管辖
    {
        int x=edge[i].to;
        res[x]=dfs2(x,1);
    }
    for (unsigned int i=0;i<u.size();i++) //(5)
    {
        int x=u[i].second,w=u[i].first;
        if (!res[x] && w<dis[x][0]) //没被管辖,且自己管辖更优
        {
            vis[x]=res[x]=1;
            del[i]=1; //删掉
        }
    }
    for (int i=head[1];i;i=edge[i].next) //(6)
    {
        int x=edge[i].to;
        if (!res[x]) v.push_back(mp(edge[i].w,x));
    }
    sort(v.begin(),v.end()); //(6):按到根的距离排序
    bool ans=1;
    for (unsigned int i=0,j=0;i<v.size();i++) //(7)
    {
        for (;j<u.size() && (u[j].first<v[i].first || del[j]);j++);
        if (j==u.size()) { ans=0; break; } //找不到能管辖的了
        j++; //使用 Uj 管辖 Vi
    }
    return ans;
}

signed main()
{
    n=read();
    ll l=0,r=0;
    for (int i=1;i<n;i++)
    {
        a=read(); b=read(); c=read();
        r+=c;
        add(a,b,c);
        add(b,a,c);
    }
    m=read();
    for (int i=1;i<=m;i++) s[i]=read();
    dfs(1,0,0);
    while (l<r) //(1):二分答案
    {
        ll mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    return !printf("%lld",l);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空