题解 P2680 【运输计划】

2018-07-25 16:16:04


对于这道题,我们先通过倍增Lca求出每条路径所用的时间。然后进行二分答案。

对于当前二分到的最短时间k,和m条路径的时间花费进行比较,对于时间比k大的路径,我们把这条路径差分一下(树上差分见博客),并记录下比k大的路径的条数cnt和这些路径的最大值max。

接下来枚举每一条边,通过差分求出这条边被比k大的路径覆盖的次数。如果这条边被覆盖了cnt次,并且max-val<=k(val为这条边的时间花费),这就表明,去掉这条边的值,就可以让所有cnt条比k大的边都能在k的时间内完成任务。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int readn() 
{
    int x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x;
}
int n,m,cnt=0,Max;
int head[1001000],nxt[1001000],to[1001000],val[1001000];
int d[1001000],f[25][1001000],dis[1001000],num[1001000];
int p[1001000];
struct road
{
    int a,b,l,dis;
}r[301000];
void addedge(int x,int y,int z)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
    val[cnt]=z;
}
void dfs(int u,int dep)
{
    d[u]=dep,p[++cnt]=u;
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(!d[v]) f[0][v]=u,dis[v]=dis[u]+val[i],dfs(v,dep+1);
    }
}
int Lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(d[f[i][x]]>=d[y]) x=f[i][x];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(f[i][x]!=f[i][y])
        {
            x=f[i][x];
            y=f[i][y];
        }
    return f[0][x];
}
bool check(int k)
{
    memset(num,0,sizeof(num));
    cnt=0;
    for(int i=1;i<=m;i++) 
        if(r[i].dis>k) num[r[i].a]++,num[r[i].b]++,num[r[i].l]-=2,cnt++;
    for(int i=n;i>=1;i--)
    {
        num[f[0][p[i]]]+=num[p[i]];
        if(dis[p[i]]-dis[f[0][p[i]]]>=Max-k && num[p[i]]==cnt) return 1;
    }
    return 0;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=readn();
    m=readn();
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        x=readn();y=readn();z=readn();
        addedge(x,y,z);
        addedge(y,x,z);
    }
    f[0][1]=0;
    cnt=0;
    dfs(1,1);
    for(int i=1;i<=23;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][f[i-1][j]];
    int L=0,R=0;
    for(int i=1;i<=m;i++)
    {
        r[i].a=readn();r[i].b=readn();
        r[i].l=Lca(r[i].a,r[i].b);
        r[i].dis=dis[r[i].a]+dis[r[i].b]-2*dis[r[i].l];
        R=max(R,r[i].dis);
    }
    Max=R;
    while(L<R)
    {
        int mid=(L+R)/2;
        if(check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d",L);
    return 0;
}