真的是假的吗?

题解 P1084 【疫情控制】
题解

emm,这题真恶心

从早上开始写,,想出思路(经Refun神的指点)后慢慢写,写了1个多小时才写完,然后一直调到下午才A,心力交瘁

倍增+贪心

其实思路并不是很难,但是实现起来的细节。。。

大致思路 :

题目要求我们要用m个点“封死”这棵树

那么显然 一个军队越往上跳控制的点就会越多

然后题目问要“封死”这棵树的话,移动距离最大的点移动的最小距离是多少 ————显然是二分时间

具体做法 :

我们就让每个军队在二分的时间内尽量向上跳,看能不能在给定的时间内跳到节点1

如果能,就先让这个军队跳上去,记录下这个军队到节点1时的剩余时间Rest和它在向上跳的路径中1的儿子Top,便于后来的处理。

如果不能,就让这个军队尽量往上跳,并在终点打上控制标记(毕竟越往上跳控制的节点肯定不会比在原来的点少)

处理完所有的军队后,我们再将所有能蹦到节点1的军队按照Rest进行从小到大的排序

然后如果这个点的Rest已经不能再从1蹦回Top了并且Top还没有被控制,那就让这个点别在节点1呆着了,直接回到Top顺便把Top节点控制了就行啦,因为如果它不回去,肯定还要有别的地方的军队来控制Top,那样显然距离更远。

最后再把所有没有被控制的节点1的儿子(注意: 如果这个点的所有子树的叶子节点被控制了,那这个点也算是被控制了)加入队列,然后再按从大到小排个序。

最后把现在仍在节点1的军队按照Rest从大到小排个序,然后和没被控制的节点一一比对就好辣

具体做法说完了,然后我们观察数据范围,n,m<=50000,暴力向上跳肯定是会T的

所以我们使用倍增进行优化

f[i][j]表示从i这个点跳 2^j 步能跳到的节点

st[i][j]表示从i这个点跳 2^j 步的距离

然后军队向上提的时候就和倍增求LCA类似,这样一来就可以A掉此题

然而,这题细节很多啊啊

各位dalao如有不懂之处也可以看一看代码,上丑陋的代码↓


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
const int M = 50005 ;
const int N = 20 ;
using namespace std;
inline int read(){
    int x=0,w=1; char c=getchar(); 
    while(c>'9'||c<'0'){ if(c=='-') w=-1 ;c=getchar() ;}
    while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar() ; }
    return x*w;
}
int hea[M],num;
int n,m;
int p[M];
int st[M][N],f[M][N],Ans;
int top[M],tdis[M];
int rnum=0;
int q[M],tail=0;
bool lea[M];
bool vis[M];
bool fs=0;
struct E{
    int nex,to;
    int dis;
}edge[M<<2];
struct Army{
    int Rest;
    int Top;
}army[M];
inline bool cmp(int a,int b){ return a>b; }
inline bool cmpmin(Army a,Army b){ return a.Rest<b.Rest; }
inline bool cmpmax(Army a,Army b){ return a.Rest>b.Rest; }
inline void add_edge(int from,int to,int dis){
    edge[++num].nex=hea[from];
    edge[num].to=to;
    edge[num].dis=dis;
    hea[from]=num;
}
void Dfs(int u,int father){
    for(int i=hea[u];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==father) continue ;
        f[v][0]=u; 
        st[v][0]=edge[i].dis;
        Dfs(v,u);
    }
}
void RMQ(){
    for(int j=1;j<=18;j++)
      for(int i=1;i<=n;i++){
        f[i][j]=f[f[i][j-1]][j-1];
        st[i][j]=st[i][j-1]+st[f[i][j-1]][j-1];
      }
}
void Dfs1(int u,int father,int topf,int dist){
    top[u]=topf;
    tdis[u]=dist;
    bool ft=0;
    for(int i=hea[u];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==father) continue ;
        ft=1;
        Dfs1(v,u,topf,dist);
    }
    if(!ft)  lea[u]=1;
}
void Dfs2(int u,int father){
    if(lea[u]){
        fs=1;
        return ;
    }
    for(int i=hea[u];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==father) continue ;
        else if(vis[v]) continue ;
        Dfs2(v,u);
        if(fs) return ;
    }
}
inline bool Look(int v){
    fs=0;
    Dfs2(v,f[v][0]);
    return fs;
}
inline bool judge(int mid){
    memset(vis,0,sizeof(vis));
    memset(q,0,sizeof(q));
    memset(army,0,sizeof(army));
    rnum=0;
    tail=0;
    for(int i=1;i<=m;i++){
        int tim=mid;
        int now=p[i];
        bool syst=0;
        while(1){
            for(int j=18;j>=0;j--){
              if(f[now][j]&&st[now][j]<=tim){
                tim-=st[now][j];
                now=f[now][j];
                break;
              }
              if(j==0||now==1){
                syst=1;
                break;
              }
            }
            if(syst) break;
        }
        if(now==1){
            army[++rnum].Top=top[p[i]];
            army[rnum].Rest=tim;
        }
        else vis[now]=1;
    }   
    sort(army+1,army+m+1,cmpmin);
    for(int i=1;i<=m;i++) 
      if(army[i].Rest<tdis[army[i].Top]){
        if(!vis[army[i].Top]&&Look(army[i].Top)){
            vis[army[i].Top]=1;
            army[i].Rest=-1;
        }
      }
    sort(army+1,army+m+1,cmpmax);
    for(int i=hea[1];i;i=edge[i].nex){
        int v=edge[i].to;
        if(!vis[v]&&Look(v))
          q[++tail]=edge[i].dis;
    }
    sort(q+1,q+tail+1,cmp);
    for(int i=1;i<=tail;i++)
      if(army[i].Rest<q[i])
        return false;
    return true; 
}
int main(){
    n=read();
    int R=0;
    for(int i=1;i<n;i++){
        int u = read(),v = read();
        int w = read();
        add_edge(u,v,w);
        add_edge(v,u,w);
        R+=w;
    }
    Dfs(1,0);
    for(int i=hea[1];i;i=edge[i].nex){
        int v=edge[i].to;
        Dfs1(v,1,v,edge[i].dis);
    }
    RMQ();
    m=read();
    for(int i=1;i<=m;i++) p[i]=read();
    int tmp=0;
    for(int i=hea[1];i;i=edge[i].nex) tmp++;
    if(tmp>m){
        printf("-1\n");
        return 0;
    }
    int L=0;
    while(L<=R){
        int mid=(L+R)>>1;
        if(judge(mid)) Ans=mid,R=mid-1;
        else L=mid+1;
    }
    printf("%d\n",Ans);
    return 0;
评论