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

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

点击量:109

学习了一下重构树。

题目背景

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

魔力之都可以抽象成一个 \(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */