无限UCW

[题解]洛谷P2680:运输计划
原题链接:P2680 运输计划总结:树上差分入门好题。题目大意:给出一棵$n$个点的树,边带边权;同时给出$m$条...
扫描右侧二维码阅读全文
26
2019/10

[题解]洛谷P2680:运输计划

原题链接:P2680 运输计划

总结:树上差分入门好题。


题目大意:给出一棵$n$个点的树,边带边权;同时给出$m$条树上路径;允许将一条边的边权钦定修改为0,最小化路径的最大值。

考虑暴力,枚举每条边,将其边权暴力修改为0后统计答案。枚举边的复杂度为$O(n)$,暴力dfs统计答案需要枚举$m$条给出的路径,对每条路径暴力求长度,则复杂度为$O(nm)$,总复杂度为$O(n^2m)$,显然不可过,考虑求长度时可以前缀和优化,统计答案降至$O(m)$,则总复杂度为$O(nm)$,仍然不可过。

暴力显然已达极限,考虑换个思路。如果修改完后的最长路长度为$x$,那么对于长度大于$x$的所有路径,必然有一条长为$maxp$的公共边,使得原本的最长路径$maxd$满足$maxd - maxp = x$。于是我们惊讶地发现如果预先知道答案,则本题异常好做,故考虑二分答案,check函数只需将上式改写为$maxd - maxp \le x$即可,若满足条件则答案符合,不满足则答案不符合;对于满足条件的答案$x$,比$x$大的答案也一定符合,对于不满足条件的答案$x$,比$x$小的答案也一定不符合,答案满足单调性,二分答案可做。

进一步考虑check函数:我们可以找出所有长度大于$x$的路径,统计这些路径经过了哪些边,贪心地寻找这些路径都经过的一条权值最大的公共边,显然,修改这条边为0一定最优,记录一下这条边的权值$maxp$,然后用上面的式子判一下即可,复杂度$O(n+m)$。

修改前的最长路径可以在$O(n)$时间内求出,记为$maxd$,则总时间复杂度为$O((n+m)\log {maxd})$。

注意在预处理时求出需要使用的lca和路径长度,本题我使用了倍增lca,但是用tarjan显然会更优,本题写倍增常数偏大,需要卡常。

R25648172 R25648222

#include<cstdio>
#include<cstring>
using namespace std;
inline void swap(int &x,int &y){int p=x;x=y;y=p;}
inline int max(int a,int b){return a>b?a:b;}
inline int isdigit(char c){return c>='0'&&c<='9';}
inline int read(){
    register int ch,flag=0,rs;
    while(!isdigit(ch=getchar()))(ch=='-')&&(flag=1);
    for(rs=ch-'0';isdigit(ch=getchar());rs=rs*10+ch-'0');
    (flag)&&(rs=-rs);
    return rs;
}
const int MAXN = 300001;
int n,m;
int hd[MAXN<<1],to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],cnt;
inline void add_edge(int u,int v,int w){to[++cnt]=v;nxt[cnt]=hd[u];val[cnt]=w;hd[u]=cnt;}
int dep[MAXN],dis[MAXN],fa[MAXN][30];
void tree(int u,int f){
    dep[u]=dep[fa[u][0]=f]+1;
    for(register int i=0;fa[u][i];++i)fa[u][i+1]=fa[fa[u][i]][i];
    for(register int i=hd[u];i;i=nxt[i])
        if(to[i]!=f){
            dis[to[i]]=dis[u]+val[i];
            tree(to[i],u);
        }
}
inline int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);
    for(register int i=20;i>=0;--i)if(dep[v]-(1<<i)>=dep[u])v=fa[v][i];
    if(u==v)return u;
    for(register int i=20;i>=0;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int dlt[MAXN],num,maxp;
inline void reset(){memset(dlt,0,sizeof(int)*(n+1));num=maxp=0;}
void getans(int u){
    for(register int i=hd[u];i;i=nxt[i]){
        if(to[i]==fa[u][0])continue;
        getans(to[i]);
        dlt[u]+=dlt[to[i]];
    }
    if(dlt[u]==num)maxp=max(maxp,dis[u]-dis[fa[u][0]]);
}
struct Route{
    int u,v,lca,dis;
}route[MAXN];
int maxd;
inline int check(int x){
    reset();
    for(register int i=1;i<=m;++i){
        if(route[i].dis>x){
            ++num;
            ++dlt[route[i].u],++dlt[route[i].v];
            dlt[route[i].lca]-=2;
        }
    }
    if(!num)return 1;
    getans(1);
    if(maxd-maxp>x)return 0;
    return 1;
}
int main(){
    //freopen("test.txt","r",stdin);
    n=read();m=read();
    for(register int i=1,u,v,w;i<n;++i){
        u=read();v=read();w=read();
        add_edge(u,v,w);add_edge(v,u,w);
    }
    tree(1,0);
    for(register int i=1;i<=m;++i){
        route[i].u=read();route[i].v=read();
        route[i].lca=lca(route[i].u,route[i].v);
        route[i].dis=dis[route[i].u]+dis[route[i].v]-(dis[route[i].lca]<<1);
        maxd=max(maxd,route[i].dis);
    }
    int l=0,r=maxd,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}
最后修改:2019 年 10 月 26 日 10 : 23 AM

发表评论