P2680 运输计划

http://www.luogu.org/problem/show?pid=2680#sub

题目背景

公元 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 号星球。

输出格式：

输出文件名为 transport.out。

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

输入输出样例

输入样例#1：

输出样例#1：

说明

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

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

【题目分析】

二分答案，如果一条航道的长度大于当前二分的答案，那么很明显这条航道上需要有一条边权值变为0，且条边权值应该>=(航道长度-二分的答案),那么若想使得所以不满足条件的航道都满足条件，这个虫洞就应该设置在这些航道的交集上，且权值应>=(max(航道长度)-二分的答案),航道的交集具体实现可以把这条航道上路径次数都加1，假设不满足条件的航道有m条，那么一条边如果次数==m条，就表示其是m条航道的交集了，实现的话一个dfs，复杂度O(nlogn)

//T—T 95
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define maxn 600100
int dp,pre[maxn],p[maxn],tt[maxn],ww[maxn],fa[maxn],deep[maxn],v[maxn],a[maxn],b[maxn],lca[maxn];
int s[maxn][20],n,m,sum[maxn],ans,cnt,dis[maxn],dist[maxn];


void gao(int x)
{
    int i=p[x];
    while(i)
    {
        if(tt[i]!=fa[x])
          gao(tt[i]),
          sum[x]+=sum[tt[i]];
        i=pre[i];
    }
    
}
int check(int x)
{
    int cnt=0,dec=0;
    for(int i=1;i<=n;i++)
      sum[i]=0;
    for(int i=1;i<=m;i++)
        if(dist[i]>x)
        {
            cnt++;
            dec=max(dec,dist[i]-x);
            sum[a[i]]++;
            sum[b[i]]++;
            sum[lca[i]]-=2;
        }
    gao(1);
    for(int i=1;i<=n;i++)
      if(sum[i]==cnt&&v[i]>=dec)
        return 1;
    return 0;
}
int getlca(int x,int y)
{
    if(deep[x]>deep[y])
      x^=y^=x^=y;
    for(int i=19;i>=0;i--)
      if(deep[y]-deep[x]>=1<<i)
        y=s[y][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--)
      if(s[x][i]!=s[y][i])
        x=s[x][i],y=s[y][i];
    return fa[x];
}
void dfs(int x)
{
    int i;
    i=p[x];
    while(i)
    {
        if(tt[i]!=fa[x])
        {
            deep[tt[i]]=deep[x]+ 1;
            fa[tt[i]]=x;
            v[tt[i]]=ww[i];
            dis[tt[i]]=dis[x]+ww[i];
            dfs(tt[i]);
        }
        i=pre[i];
    }
}
void add(int x,int y,int z)
{
    dp++;
    pre[dp]=p[x];
    p[x]=dp;
    tt[dp]=y;
    ww[dp]=z;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      s[i][0]=fa[i];
    for(int i=1;i<20;i++)
      for(int j=1;j<=n;j++)
        s[j][i]=s[s[j][i-1]][i-1];
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        lca[i]=getlca(a[i],b[i]);
        dist[i]=dis[a[i]]+dis[b[i]]-2*dis[lca[i]];
    }
    int l=0,r=0;
    for(int i=1;i<=m;i++)
      r=max(r,dist[i]);
    int mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d
",l);
    return 0;
}