洛谷 P2680 NOIP2015提高组 运输计划 题解【tarjan】【二分答案】【LCA】

作者: wjyyy 分类: LCA,tarjan,二分,解题报告 发布时间: 2018-06-07 11:29

点击量:61

非常的卡常数? 拿了好长时间的95分。。

题目描述

    公元2044年,人类进入了宇宙纪元。L国有n个星球,还有n−1条双向航道,每条航道建立在两个星球之间,这n−1条航道连通了L国的所有星球。小P掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从ui号星球沿最快的宇航路径飞行到vi号星球去。显然,飞船驶过一条航道是需要时间的,对于航道j,任意飞船驶过它所花费的时间为tj,并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新, L国国王同意小P的物流公司参与L国的航道建设,即允许小P把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。在虫洞的建设完成前小P的物流公司就预接了m个运输计划。在虫洞建设完成后,这m个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。如果小P可以自由选择将哪一条航道改造成虫洞, 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

 

输入描述

    第一行包括两个正整数 n,m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。接下来 n−1 行描述航道的建设情况,其中第 i 行包含三个整数 ai,bi 和 ti,表示第 i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。数据保证 1<=ai,bi<=n 且 0<=ti<=1000。接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1<=ui,vi<=n

输出描述

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

样例输入

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

样例输出

11

样例解释:

将第 1 条航道改造成虫洞: 则三个计划耗时分别为:11,12,11,故需要花费的时间为 12。

将第 2 条航道改造成虫洞: 则三个计划耗时分别为:7,15,11,故需要花费的时间为 15。

将第 3 条航道改造成虫洞: 则三个计划耗时分别为:4,8,11,故需要花费的时间为 11。

将第 4 条航道改造成虫洞: 则三个计划耗时分别为:11,15,5,故需要花费的时间为 15。

将第 5 条航道改造成虫洞: 则三个计划耗时分别为:11,10,6,故需要花费的时间为 11。

故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短,需要花费的时间为 11。

测试数据及约定:

测试点编号 n= m= 约定
1 100 1
2 100 100 第i条航道连接i号星球与i+1号星球
3 100 100
4 2000 1
5 1000 1000 第i条航道连接i号星球与i+1号星球
6 2000 2000 第i条航道连接i号星球与i+1号星球
7 3000 3000 第i条航道连接i号星球与i+1号星球
8 1000 1000
9 2000 2000
10 3000 3000
11 80000 1
12 100000 1
13 70000 70000 第i条航道连接i号星球与i+1号星球
14 80000 80000 第i条航道连接i号星球与i+1号星球
15 90000 90000 第i条航道连接i号星球与i+1号星球
16 100000 100000 第i条航道连接i号星球与i+1号星球
17 80000 80000
18 90000 90000
19 100000 100000
20 300000 300000
所有数据 1 <= ai, bi, uj, vj <= n, 0 <= ti <= 1000

   首先这个题看上去送了很多分,首先有40分的链,和20分的m=1,这60分是很好拿的,前40分在链上做差分再存一下状态就可以了,后20分直接在这条线路上枚举删掉最长边。

 

    正确算法:我们需要找的是一条边,把这条边的权值改为0,使最长链最短。(咦这不是二分答案吗)

               但是需要注意一点,如果直接改变最长链上的最长边,使最长链变得尽可能短,但此时次长链可能没有改变,所以不能直接利用贪心做,接下来我们介绍二分答案的过程。

 

     二分答案的上界是最长链的长度,如果删掉的边权为0,答案就是这个,因此把这个作为枚举边界。而我们也可以将下界优化一下,优化到最长链减最长边。二分答案中检验的值,是可容纳的最长时间,对大于mid的链上,我们还需要找一条边,使得所有大于mid的链都经过这条边。(如果找不到一条这样的边,说明mid不合法,直接return false;)。然后在所有满足条件的边中,枚举找到边权最大的边,用最长链减去这条边作为待检验答案。如果仍然大于mid,则mid不合法,如果小于mid,则合法,return false。直到枚举到一个mid使得不能有更优解让mid-1合法。

 

    还有一个优化是求树上两点之间的距离,如果其中一个点是另一个点的祖先,那么可以用深度较大的节点到根节点的距离(这个距离是可以预处理出来的)减去深度较浅的根节点距离。如果不是祖先关系,则用它们到根节点的距离之和减去二倍的LCA到根节点的距离,也就是前缀和的思想。

Code:

#include<cstdio>
#include<cstring>
#include<iostream>
struct node
{
    int n,v,ext;
    node *nxt;
    node (int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[300010],*tail[300010];

struct Node
{
    int n,cnt;
    bool used;
    Node *nxt;
    Node(int n,int cnt)
    {
        this->cnt=cnt;
        this->n=n;
        nxt=NULL;
    }
    Node()
    {
        nxt=NULL;
    }
};
Node Head[300010],*Tail[300010];
int s[300010];
std::pair<int,int> fa[300010];//fa是直接父亲和到直接父亲的距离
int d[300010];
int n,m,r=0;
bool vis[300010],used[300010],Used[300010];
struct Ask
{
    int s,t;
    int ans,anc;
    Ask(int s,int t)
    {
        this->s=s;
        this->t=t;
    }
    Ask(){}
}ask[300010];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
int up[300010];//到根结点的距离(前缀和思想)
int query(int x,int y,int lca)
{
    return up[x]+up[y]-2*up[lca];
}
void tarjan(int x,int from)
{
    vis[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(Used[p->n])
            continue;
        up[p->n]=up[x]+p->v;
        Used[p->n]=true;
        fa[p->n].first=x;
        fa[p->n].second=p->v;
        tarjan(p->n,x);
    }
    Node *P=&Head[x];
    while(P->nxt!=NULL)
    {
        P=P->nxt;
        if(vis[P->n]&&!used[P->cnt])
        {
            used[P->cnt]=true;
            ask[P->cnt].anc=my_find(P->n);
            ask[P->cnt].ans=query(P->n,x,ask[P->cnt].anc);//求这条链的长度
            if(ask[P->cnt].ans>r)
                r=ask[P->cnt].ans;
        }
    }
    s[x]=from;
}
int minn=999999999,delta=0;//minn一定要大于300000000,不然常数就算优化了也会卡数据大小。
int tmp=0,longest=0,maxx=0;
void DFs(int x)
{
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(used[p->n])
            continue;
        used[p->n]=true;
        DFs(p->n);
        d[x]+=delta;
        delta=0;
    }
    delta+=d[x];//这里是差分的做法
    if(delta==tmp)
        if(longest-fa[x].second<minn)
            minn=longest-fa[x].second;
    return;
}
bool check(int mid)
{
    memset(d,0,sizeof(d));
    tmp=0;
    for(int i=1;i<=m;i++)//打差分
        if(ask[i].ans>mid)
        {
            d[ask[i].s]++;
            d[ask[i].t]++;
            d[ask[i].anc]-=2;
            tmp++;
        }
    minn=999999999;
    memset(used,0,sizeof(used));
    delta=0;
    used[1]=true;
    DFs(1);
    if(minn>mid)
        return false;
    return true;
}
void work()
{
    for(int i=1;i<=m;i++)
        if(ask[i].ans>longest)//求最长链,优化二分下界
            longest=ask[i].ans;
    int l=longest-maxx,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d\n",l);
    return;
}
int read()//读入优化
{
    char c=getchar();int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x;
}
int main()
{
    //freopen("transport.in","r",stdin);
    up[0]=0;
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(used,0,sizeof(used));
    memset(Used,0,sizeof(Used));
    int u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        s[i]=i;
        tail[i]=&head[i];
        Tail[i]=&Head[i];
    }
    for(int i=1;i<n;i++)
    {
        u=read();
        v=read();
        w=read();
        //scanf("%d%d%d",&u,&v,&w);
        tail[u]->nxt=new node(v,w);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u,w);
        tail[v]=tail[v]->nxt;
        if(w>maxx)
            maxx=w;
    }
    for(int i=1;i<=m;i++)
    {
        u=read();
        v=read();
        //scanf("%d%d",&u,&v);
        ask[i]=Ask(u,v);//初始化询问
        Tail[u]->nxt=new Node(v,i);
        Tail[u]=Tail[u]->nxt;
        Tail[v]->nxt=new Node(u,i);
        Tail[v]=Tail[v]->nxt;
    }
    Used[1]=true;
    tarjan(1,1);//假定1为根节点
    work();
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */