Luogu P1084 [NOIP2012]疫情控制

题目
首先我们二分一下答案。
然后我们用倍增让军队往上跳，最多先跳到根的子节点。
如果当前军队可以到达根节点，那么记录一下它的编号和它到达根节点后还可以走的时间。
并且我们记录根节点的叶子节点上到根节点后剩余时间最短的军队。
如果不可以到达根节点，那么在它跳到的节点设置检查点。
如果一个节点建立了检查点或者它的所有子树都设立了检查点，则说明以这个节点为根的子树已经被封死。记录根节点的所有子树中，未被封死的子树。
将我们已经记录好了的可以到根节点的军队按照剩余时间从大到小排序。
将未被封死的子树按照到子树到根节点的距离从大到小排序。
然后依次处理未被封死的子树要由哪支军队来管辖。
离根节点远的子树由剩余时间大的军队来管辖是没有问题的，不过更优的是由本来就在这棵子树上的军队来管辖。
所以我们先查看我们事先记录的（在子树中可以到达根节点，且到根节点后剩余时间最小的军队）是否被使用，如果被使用，再看当前没有被使用的军队里剩时间最大的可否到达这棵子树。

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace IO
{
    char ibuf[(1<<21)+1],*iS,*iT;
    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
    int read(){int x=0;char ch=Get();while(ch>57||ch<48)ch=Get();while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return x;}
}
using namespace IO;
const int N=50007;
vector<P>E[N];
int pos[N],F[N][20],f[N],vis[N],used[N],r[N],n,m,cnt1,cnt2;
LL d[N][20];
struct node{int r,id;}a[N],b[N];
int operator<(node a,node b){return a.r>b.r;}
void dfs(int u,int fa,int dis)
{
    F[u][0]=fa,d[u][0]=dis;
    for(int i=1;i<=17;++i) F[u][i]=F[F[u][i-1]][i-1],d[u][i]=d[u][i-1]+d[F[u][i-1]][i-1];
    for(P p:E[u]) if(p.fir^fa) dfs(p.fir,u,p.sec);
}
int checkd(int u,int fa)
{
    int f1=1,f2=0;
    if(vis[u]) return 1;
    for(P p:E[u])
    {
        if(p.fir==fa) continue;
    f2=1;
    if(!checkd(p.fir,u))
    {
            f1=0;
            if(u==1) b[++cnt2]=(node){p.sec,p.fir};
            else return 0;
        }
    }
    return f1&f2;
}
int check(int T)
{
    cnt1=cnt2=0,memset(vis,0,sizeof vis),memset(f,0,sizeof f),memset(used,0,sizeof used);int i,j,u,s;
    for(i=1;i<=m;++i)
    {
    for(u=pos[i],s=0,j=17;~j;--j) if(F[u][j]>1&&d[u][j]+s<=T) s+=d[u][j],u=F[u][j];
    if(F[u][0]==1&&d[u][0]+s<=T)
    {
        a[++cnt1]=(node){T-s-d[u][0],i};
            if(!f[u]||a[cnt1].r<r[u]) r[u]=a[cnt1].r,f[u]=i;
        }
        else vis[u]=1;
    }
    if(checkd(1,0)) return 1;
    sort(a+1,a+1+cnt1),sort(b+1,b+1+cnt2),u=used[0]=1;
    for(i=1;i<=cnt2;++i)
    {
        if(!used[f[b[i].id]]){used[f[b[i].id]]=1;continue;}
        while(u<=cnt1&&(used[a[u].id]||a[u].r<b[i].r)) ++u;
        if(u>cnt1) return 0;
    used[a[u].id]=1;
    }
    return 1;
}
main()
{
    n=read();int i,u,v,w,l=0,r=2e9,ans=-1,mid;
    for(i=1;i<n;++i) u=read(),v=read(),w=read(),E[u].pb(P(v,w)),E[v].pb(P(u,w));
    dfs(1,0,0),m=read();
    for(i=1;i<=m;++i) pos[i]=read();
    while(l<=r) check(mid=l+r>>1)? ans=mid,r=mid-1:l=mid+1;
    return !printf("%d",ans);
}

巴特西

Luogu P1084 [NOIP2012]疫情控制

最新文章

热门文章