洛谷 P4768 [NOI2018]归程 题解【Kruskal重构树】【倍增】

作者: wjyyy 分类: dfs序,倍增,图论,生成树,解题报告 发布时间: 2019-02-21 21:09

点击量:422

学习了一下重构树。

题目背景

本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 $ n$ 个节点、 $ m$ 条边的无向连通图(节点的编号从 $ 1$ 至 $ n$)。我们依次用 $ l,a$ 描述一条边的长度海拔

作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边

我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。

题目描述

Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。

Yazid 的家恰好在魔力之都的 $ 1$ 号节点。对于接下来 $ Q$ 天,每一天 Yazid 都会告诉你他的出发点 $ v$ ,以及当天的水位线 $ p$。

每一天, Yazid 在出发点都拥有一辆。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

  • 需要特殊说明的是,第二天车会被重置,这意味着:
    • 车会在新的出发点被准备好。
    • Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

本题的部分测试点将强制在线,具体细节请见【输入格式】和【子任务】。

输入格式

从文件 return.in 中读入数据。

单个测试点中包含多组数据。输入的第一行为一个非负整数 $ T$,表示数据的组数。

接下来依次描述每组数据,对于每组数据:

  • 第一行 $ 2$ 个非负整数 $ n,m$,分别表示节点数、边数。
  • 接下来 $ m$ 行,每行 $ 4$ 个正整数 $ u,v,l,a$,描述一条连接节点 $ u,v$ 的、长度为 $ l$、海拔为 $ a$ 的边。
    • 在这里,我们保证 $ 1≤u,v≤n$。
  • 接下来一行 $ 3$ 个非负数 $ Q,K,S$,其中 $ Q$ 表示总天数,$ K\in{0,1}$ 是一个会在下面
    被用到的系数, $ S$ 表示的是可能的最高水位线。
  • 接下来 $ Q$ 行依次描述每天的状况。每行 $ 2$ 个整数 $ v_0,p_0$ 描述一天:
    • 这一天的出发节点为 $ v=(v_0+K\times lastans – 1) \bmod n+1$。
    • 这一天的水位线为 $ p=(p_0+K\times lastans) \bmod (S + 1)$。
    • 其中 $ lastans$ 表示上一天的答案(最小步行总路程)。特别地,我们规定第 $ 1$ 天时 $ lastans=0$。
    • 在这里,我们保证 $ 1\le v_0\le n, 0\le p_0\le S$。

对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。

输出格式

输出到文件 return.out 中。
依次输出各组数据的答案。对于每组数据:

  • 输出 $ Q$ 行每行一个整数,依次表示每天的最小步行总路程。

输入输出样例

【样例 1 输入】

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

【样例 1 输出】

0
50
200
50
150 

【样例 1 解释】
第一天没有降水,Yazid 可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同,均为连接 $ 1,2$ 号节点的边、连接 $ 3,4$ 号
点的边有积水。

对于第二天, Yazid 从 $ 2$ 号点出发坐车只能去往 $ 3$ 号节点,对回家没有帮助。因此 Yazid 只能纯靠徒步回家。

对于第三天,从 $ 4$ 号节点出发的唯一一条边是有积水的,车也就变得无用了。 Yazid 只能纯靠徒步回家。

对于第四天, Yazid 可以坐车先到达 $ 2$ 号节点,再步行回家。

第五天所有的边都积水了,因此 Yazid 只能纯靠徒步回家。

【样例 2 输入】

1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0

【样例 2 输出】

0 
2 
3 
1

【样例 2 解释】

本组数据强制在线。

第一天的答案是 $ 0$,因此第二天的 $ v=(5+0-1) \bmod 5+1=5$,$ p=(2+0) \bmod (3+1)=2$。

第二天的答案是 $ 2$,因此第三天的 $ v=(2+2-1) \bmod 5+1=4$,$ p=(0+2) \bmod (3+1)=2$。

第三天的答案是 $ 3$,因此第四天的 $ v=(4+3-1) \bmod 5+1=2$,$ p=(0+3) \bmod (3+1)=3$。

子任务

所有测试点均保证 $ T\le 3$,所有测试点中的所有数据均满足如下限制:

  • $ n\le 2\times 10^5$,$ m\le 4\times 10^5​$,$ Q\le 4\times 10^5$,$ K\in{0,1}$,$ 1\le S\le 10^9​$。
  • 对于所有边: $ l\le 10^4$,$ a\le 10^9$。
  • 任意两点之间都直接或间接通过边相连。

为了方便你快速理解,我们在表格中使用了一些简单易懂的表述。在此,我们对这些内容作形式化的说明:

  • 图形态:对于表格中该项为“一棵树”或“一条链”的测试点,保证 $ m=n-1$。
    除此之外,这两类测试点分别满足如下限制:

    • 一棵树:保证输入的图是一棵树,即保证边不会构成回路。
    • 一条链:保证所有边满足 $ u+1=v$。
  • 海拔:对于表格中该项为“一种”的测试点,保证对于所有边有 $ a=1$。

  • 强制在线:对于表格中该项为“是”的测试点,保证 $ K=1$;如果该项为“否”,则有 $ K=0$。

  • 对于所有测试点,如果上述对应项为“不保证”,则对该项内容不作任何保证。

$ n$ $ m$ $ Q\le$ 测试点 图形态 海拔 强制在线
$ \le 1$ $ \le 0$ $ 0$ 1 不保证 一种
$ \le 6$ $ \le 10$ $ 10$ 2
$ \le 50$ $ \le 150$ $ 100$ 3
$ \le 100$ $ \le 300$ $ 200$ 4
$ \le 1500$ $ \le 4000$ $ 2000$ 5
$ \le 200000$ $ \le 400000$ $ 100000$ 6
$ \le 1500$ $ =n-1$ $ 2000$ 7 一条链 不保证
8
9
$ \le 200000$ $ 100000$ 10 一棵树
11
$ \le 400000$ 12 不保证
13
14
$ \le 1500$ $ \le 4000$ $ 2000$ 15
16
$ \le 200000$ $ \le 400000$ $ 100000$ 17
18
$ 400000$ 19
20

题解:

重构树可以在这篇博客(by 守望)里学习(因为整体架构比较简单我就没写学习笔记……)

这个题是要求每天走的边大于一个值 $ S$。因此我们先把边按海拔从大到小排序。

然后对于每条连接不同联通块的边,新建一个点,点权为这条边边权,与这条边的两个点相连。

这样连出来的一定是一棵树,并且最后新建的点是根。

此时随着深度变大,点权非严格递减。因此当询问 $ S$ 时可以倍增出当前点 $ v$ 的祖先中深度最浅的满足点权 $ > S$ 的点。

进行这一步操作前需要对重构树dfs一遍,存下以每个点为根,子树中到 $ 1$ 号节点距离最近的点,答案就是这个距离。

距离直接从 $ 1$ 号点出发跑一遍 dijkstra 即可。(SPFA会被卡(甚至已经是梗了)

Code:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using std::priority_queue;
struct Edge
{
    int u,v,w,x;
    Edge(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
    Edge(){}
    friend bool operator <(Edge a,Edge b)
    {return a.w>b.w;}
}E[400100];
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[800100];
int head[400100],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}

struct sta
{
    int n,dis;
    sta(int n,int dis)
    {
        this->n=n;
        this->dis=dis;
    }
    sta(){}
    friend bool operator <(sta a,sta b)
    {
        return a.dis>b.dis;
    }
};
int dis[400100];
int s[400100],scnt;
int Find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=Find(s[x]);
}
void Union(int x,int y)
{
    s[Find(y)]=Find(x);
}
int F[20][400100],h[400100];
void dfs(int x,int from)
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            dfs(e[i].n,x);
            dis[x]=dis[x]<dis[e[i].n]?dis[x]:dis[e[i].n];
        }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(head,-1,sizeof(head));
        memset(dis,0x3f,sizeof(dis));
        ecnt=-1;
        int n,m,Q,k,u,v,w,x,lstans=0;
        scanf("%d%d",&n,&m);
        scnt=n;
        for(int i=1;i<=n+n-1;++i)
            s[i]=i;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d%d",&u,&v,&w,&x);
            E[i]=Edge(u,v,x);
            add(u,v,w);
        }
        std::sort(E+1,E+1+m);
        priority_queue<sta> q;
        dis[1]=0;
        q.push(sta(1,0));
        while(!q.empty())
        {
            sta k=q.top();
            q.pop();
            if(k.dis>dis[k.n])
                continue;
            for(int i=head[k.n];~i;i=e[i].nxt)
                if(dis[e[i].n]>k.dis+e[i].v)
                {
                    dis[e[i].n]=k.dis+e[i].v;
                    q.push(sta(e[i].n,dis[e[i].n]));
                }
        }
        memset(head,-1,sizeof(head));
        ecnt=-1;
        for(int i=1;i<=m&&scnt<n+n-1;++i)
        {
            int U=Find(E[i].u),V=Find(E[i].v);
            if(U!=V)
            {
                ++scnt;
                Union(scnt,U);
                Union(scnt,V);
                F[0][U]=scnt;
                F[0][V]=scnt;
                add(U,scnt,1);
                add(V,scnt,1);
                h[scnt]=E[i].w;
            }
        }
        F[0][scnt]=scnt;
        dfs(scnt,scnt);
        for(int i=1;i<=18;++i)
            for(int j=1;j<=scnt;++j)
                F[i][j]=F[i-1][F[i-1][j]];
        scanf("%d%d%d",&Q,&k,&w);
        for(int i=1;i<=Q;++i)
        {
            scanf("%d%d",&u,&v);
            u=(u+k*lstans-1)%n+1;
            v=(v+k*lstans)%(w+1);
            for(int j=18;j>=0;--j)
                if(h[F[j][u]]>v)
                    u=F[j][u];
            lstans=dis[u];
            printf("%d\n",lstans);
        }
    }
    return 0;
}

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

… [Trackback]

[…] Here you will find 95046 more Info to that Topic: wjyyy.top/3267.html […]

trackback

… [Trackback]

[…] Find More on that Topic: wjyyy.top/3267.html […]

/* */