luoguP1084 疫情控制(题解)(搜索+贪心)

luoguP1084 疫情控制 题目

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define il inline

#define rg register

#define ll long long

#define N 60000

#define inf 2147483647

using namespace std;

int n,m,hd[N],cnt,u,v,w;

int c,idx[N];

int le,ri=;

int dis[N][],up[N][];

int ok[N],use[N],vis[N];

struct S{

    int res,idx;

}ne[N],to[N];

struct T{

    int nt,to,w;

}edge[N<<];

il void re(rg int &x);

void add(rg int fm,rg int to,rg int w);

void ST(rg int i,rg int fa);

int check(rg int lim);

int Dfs(rg int u,rg int fa);

int Cmp(const S &x,const S &y);

int main()

{

    re(n);

    for(rg int i=;i<n;++i)

    {

        re(u),re(v),re(w);

        add(u,v,w),add(v,u,w);

        if(u==||v==)c++;

    }

    re(m);

    if(m<c){cout<<-;return ;}

    for(rg int i=;i<=m;++i)

        re(idx[i]);

    ST(,);

    for(rg int k=;k<=;++k)

    {

        for(rg int i=;i<=n;++i)

        {

            up[i][k]=up[up[i][k-]][k-];

            dis[i][k]=dis[up[i][k-]][k-]+dis[i][k-];

        }

    }

    while(le<ri)

    {

        rg int mid=((le+ri)>>);

        if(check(mid))ri=mid;

        else le=mid+;

    }

    cout<<le;

    return ;

}

il void re(rg int &x)

{

    rg int res=;rg int w=;char c=getchar();

    while((c<''||c>'')&&c!='-')c=getchar();

    if(c=='-')w=-,c=getchar();

    while(c>=''&&c<='')res=(res<<)+(res<<)+c-'',c=getchar();

    x=w*res;

}

void add(rg int fm,rg int to,rg int w)

{

    edge[++cnt].nt=hd[fm];

    edge[cnt].to=to;

    edge[cnt].w=w;

    hd[fm]=cnt;

}

void ST(rg int i,rg int fa)

{

    up[i][]=fa;

    for(rg int k=hd[i];k;k=edge[k].nt)

    {

        rg int qw=edge[k].to;

        if(qw==fa)continue;

        dis[qw][]=edge[k].w;

        ST(qw,i);

    }

}

int check(rg int lim){

    memset(ok,,sizeof(ok));

    memset(use,,sizeof(use));

    memset(vis,,sizeof(vis));

    rg int cnt1=,cnt2=;

    rg int top=;

    for(rg int i=;i<=m;++i){

        rg int res=lim,u=idx[i];

        for(rg int k=;k>=;--k){

            if(up[u][k]&&up[u][k]!=&&res>=dis[u][k])

                res-=dis[u][k],u=up[u][k];

        }

        if(up[u][]==&&res>dis[u][])

        {

            to[++cnt1].res=res-dis[u][];

            to[cnt1].idx=u;

        }

        else ok[u]=;

    }

    Dfs(,);

    for(rg int k=hd[];k;k=edge[k].nt){

        rg int qw=edge[k].to;

        if(!ok[qw]){

            ne[++cnt2].res=dis[qw][];

            ne[cnt2].idx=qw;

        }

    }

    sort(to+,to+cnt1+,Cmp);

    sort(ne+,ne+cnt2+,Cmp);

    if(cnt1<cnt2)return ;

    for(rg int i=;i<=cnt1;++i)

    {

        if(!vis[to[i].idx])

        {

            vis[to[i].idx]=;

            continue;

        }

        while(vis[ne[top].idx])top++;

        if(to[i].res>=ne[top].res)

        {

            vis[ne[top].idx]=,top++;

            continue;

        }

        if(top>cnt2)break;

    }

    while(vis[ne[top].idx])top++;

    if(top<=cnt2)return ;

    return ;

}

int Dfs(rg int u,rg int fa)

{

    rg int temp=,flag=;

    for(rg int k=hd[u];k;k=edge[k].nt)

    {

        rg int qw=edge[k].to;

        if(qw==fa)continue;

        flag++,temp&=Dfs(qw,u);

    }

    if(!flag)temp=;

    ok[u]=(ok[u]|temp);

    if(ok[u]&&up[u][]==)

        vis[u]=;

    return ok[u];

}

int Cmp(const S &x,const S &y){return x.res<y.res;}