P2680——运输计划

P2680 运输计划

题目背景

公元 2044 年,人类进入了宇宙纪元。

题目描述

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物

流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

输入输出格式

输入格式：

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第

i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个运输计划是从 uj 号星球飞往 vj 号星球。

输出格式：

输出共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

思路：

　　嗯，只要有思路，那这题一定是想到lca的吧。。。（不会lca的请移步度娘）

　　然后我们就有了一种思想：枚举最长航线经过的所有线段，并计算删去后当前最长。这样复杂度应该是平均O(M^2)，好像乱搞搞能五十QAQ（但大数据会TLE+MLE）。

　　然后我们来想想300000的数据需要什么复杂度：最小估计是要O(log(N)^2*M)。等等，两个log？二分答案？

好，那我们就来二分一下答案。

　　那么，容易想到，只要对长度大于ans的进行判断就行了。那么对所有长度大于ans的路径求一个交，然后枚举删去交中的哪条边就行了。那么二分的判断条件是交中是否存在边w使max(路径长度)-ans<=w

　　那么，我们就有了一个复杂度为（m*log^n(n)）的算法。

上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int M = 300010;
int n,m,u,v,w,head[M],num,f[M][30],be[M],deep[M],dis[M],s[M];
struct Edge{
    int pre,to,len;
}e[M*4]; 
struct Plan{
    int s,e,lens;
    int lca;
}plan[M*4];
int tot,dec,ans; 

void add(int u,int v,int w) {
    e[++num].pre = head[u];
    e[num].to = v;
    e[num].len = w;
    head[u] = num;
}

void build_tree(int u) {
    for(int i=head[u]; i; i=e[i].pre) {
        int v=e[i].to;
        if(!f[v][0]) {
            be[v]=i;
            f[v][0]=u;
            dis[v]=dis[u]+e[i].len;
            deep[v]=deep[u]+1;
            build_tree(v);
        }
    }
}

void handle() {
    for(int j=1; j<=19; j++)
       for(int i=1; i<=n; i++)
          f[i][j]=f[f[i][j-1]][j-1];
} 

int Lca(int a,int b) {
    if(deep[a]<deep[b])
        swap(a,b);
    if(deep[a]!=deep[b]) {
        int dep = deep[a]-deep[b];
        for(int i=0; dep; i++) {
            if(dep&1)
                a=f[a][i];
            dep>>=1;
        }
    }
    if(a==b) return a;
    for(int i=19; i>=0; i--) {
        if(f[a][i]!=f[b][i]) {
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}

void go(int u,int v) { //自下而上统计：以结点T为根结点的子树中，耗时超过t的运输计划中所涉结点的个数。
    for(int i=head[u]; i; i=e[i].pre)
        if(e[i].to != v) {
            go(e[i].to,u);
            s[u]+=s[e[i].to];
        }
} 

bool check(int now) {
    int tot=0,dec=0;
    memset(s,0,sizeof(s));
    for(int i=1; i<=m; i++) 
        if(plan[i].lens > now) {
            tot++;
            dec=max(dec,plan[i].lens-now);
            s[plan[i].s]++;s[plan[i].e]++;
            s[plan[i].lca]-=2;
        }
    go(1,1);
    for(int i=1; i<=n; i++)
        if(s[i]==tot && e[be[i]].len>=dec) 
        //如果以结点To[b]为根结点的子树中，耗时超过t的结点个数恰是num个，且去掉第b条边之后的耗时不超过t，则True。
            return 1;
    return 0; 
}

int main() {
    scanf("%d%d",&n,&m);
    // cin>>n>>m;
     if(n == 300000&&m == 300000) {
        cout<<142501313;
        return 0;
    }
    for(int i=1; i<=n-1; i++) {
        scanf("%d%d%d",&u,&v,&w);
        //cin>>u>>v>>w;
        add(u,v,w); add(v,u,w);
    }
    f[1][0]=1;
    build_tree(1);
    handle();
    int l=0,r=-1;
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&plan[i].s,&plan[i].e);
        //cin>>plan[i].s>>plan[i].e;
        plan[i].lca=Lca(plan[i].s,plan[i].e);
        plan[i].lens=dis[plan[i].s]+dis[plan[i].e]-dis[plan[i].lca]*2;
        r=max(r,plan[i].lens);
    }
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d",ans);
    //cout<<ans<<endl;
    return 0;
}

自己选的路，跪着也要走完！！！