Luogu P1084 疫情控制 题解

Link

Luogu Problem view

Describe

有一棵以$1$为根节点的树,现在要在除根节点外的点设立阻拦,使得没有一条路径可以从根节点到任意一个叶子节点。这些阻拦需要$m$个军队来设立,这$m$个军队中第$i$个一开始在点$q_i$上,军队移动的时间等于移动经过的边权之和,问最少要多少时间才能设立完阻拦。注意:不同的军队可以同时移动。
对于$100%$的数据,$2\leq m\leq n\leq 50,000,0\leq w\leq {10}^9$($w$表示边权)。

Solution

由题意可知,要求的是最少的时间,所以显而易见可以二分(如果花了更长的时间肯定更可以),接下来就只需要考虑如何写$check$函数。
我们有一个贪心的想法:因为要阻拦从根到叶子节点的路径,所以军队越往上肯定就越好,这样可以阻拦更多的路径。
如果一个军队可以走到根节点,则将这个军队先放一放,因为这个军队可能会走到另一个以根节点的子节点为根的树中去。
如果一个军队不可以走到根节点,则走到能走到的深度最小的点上。
经过这次操作后,再遍历一次,记录还是可以到达的叶子节点。再贪心的思想:剩余时间最少的军队到叶子节点肯定是最优的,然后再操作一遍,把剩余节点按照到根节点的距离进行排序。
现在可能还有一些军队还未设立阻拦,将这些军队按照剩余的时间进行排序,然后与刚刚排序过的剩余的节点一一匹配,这也是个贪心策略,如果所有都能够被匹配则可行,否则不可行。

Code

#include<bits/stdc++.h>
using namespace std;

#define re register 
#define N 50010
#define int long long 
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout)

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;

int n,m,logn,q[N];
vector<pair<int,int> > a; 
vector<int> v,g;

class Edge{
    public:
        int fir[N],nxt[N*2],son[N*2],w[N*2],tot;
        inline void add(int x,int y,int z){
            ++tot;
            nxt[tot]=fir[x];
            fir[x]=tot;
            son[tot]=y;
            w[tot]=z;
        }
}E;

class LCA{
    public:
        int f[N][25],dis[N][25],dep[N];
        inline void init(int x,int fa){
            dep[x]=dep[fa]+1;
            for(int i=0;i<logn;i++) f[x][i+1]=f[f[x][i]][i];
            for(int i=0;i<logn;i++) dis[x][i+1]=dis[x][i]+dis[f[x][i]][i];
            for(int to,i=E.fir[x];i;i=E.nxt[i]){
                to=E.son[i];
                if(to==fa) continue ;
                f[to][0]=x;dis[to][0]=E.w[i];
                init(to,x);
            }
        }
}L;

class Solve{
    private:
        int l,r,mid,ans,vis[N],una[N];
    public:
        inline int dfs(int x,int fa){
            if(vis[x]==1) return 1;
            re bool ff=0;
            for(int to,i=E.fir[x];i;i=E.nxt[i]){
                to=E.son[i];
                if(to==fa) continue ;
                ff=1;
                if(dfs(to,x)==0) return 0;
            }
            return ff;
        }
        inline int check(int Max){
            a.clear();
            v.clear();
            g.clear();
            memset(vis,0,sizeof(vis));
            memset(una,0,sizeof(una));
            for(int i=1;i<=m;i++){
                re int x=q[i],cnt=0;
                for(int j=logn;j>=0;j--){
                    if(L.f[x][j]>1&&cnt+L.dis[x][j]<=Max){
                        cnt+=L.dis[x][j];
                        x=L.f[x][j];
                    }
                }
                if(L.f[x][0]==1&&cnt+L.dis[x][0]<=Max) a.push_back(make_pair(Max-(cnt+L.dis[x][0]),x));
                else vis[x]=1;
            }
            for(int to,i=E.fir[1];i;i=E.nxt[i]){
                to=E.son[i];
                if(dfs(to,1)==0) una[to]=1;
            }
            sort(a.begin(),a.end());
            for(auto i=a.begin();i!=a.end();i++){
                if(una[(*i).second]==1&&(*i).first<L.dis[(*i).second][0]) una[(*i).second]=0;
                else v.push_back((*i).first); 
            }
            for(int to,i=E.fir[1];i;i=E.nxt[i]){
                to=E.son[i];
                if(una[to]==1) g.push_back(L.dis[to][0]); 
            }
            if(v.size()<g.size()) return 0;
            sort(v.begin(),v.end());
            sort(g.begin(),g.end());
            auto i=g.begin(),j=v.begin();
            while(i!=g.end()&&j!=v.end()){
                if((*j)>=(*i)) i++,j++;
                else j++;
            }
            return i==g.end();
        }
        inline void init(){
            n=I.read();logn=log2(n)+1;l=r=0;ans=-1;
            for(int x,y,z,i=1;i<n;i++){
                x=I.read(),y=I.read(),z=I.read();r+=z;
                E.add(x,y,z);
                E.add(y,x,z);
            }
            m=I.read();
            for(int i=1;i<=m;i++) q[i]=I.read();
            L.init(1,0);
        }
        inline void solve(){
            while(l<=r){
                mid=l+r>>1;
                if(check(mid)) ans=mid,r=mid-1;
                else l=mid+1;
            }
            I.write(ans);putchar('\n');
        }
}S;
signed main(){S.init();S.solve();}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇