首页 > 其他分享 >逛森林 题解

逛森林 题解

时间:2023-06-05 17:02:06浏览次数:46  
标签:重链 int 题解 类边 dis 入点 include 森林

P5344 逛森林

题目大意

原题的题目大意已经很明确了要这个干嘛

给定一些孤立点,将要进行两种操作:

  • 若两点之间不可以通过 \(1\) 类边连通,则在两点之间连双向 \(1\) 类边

  • 若 \(u_1,v_1\) 和 \(u_2,v_2\) 均可以通过 \(1\) 类边连通,则从 \(u_1\to v_1\) 的唯一路径上的所有点均向 \(u_2\to v_2\) 的唯一路径上的所有点连单向非 \(1\) 类边。

在完成所有操作后求出从给定的 \(s\) 出发的单源最短路。

前置知识

如果你不熟悉以下内容,那还是换一篇题解看吧。

  • 树链剖分

  • 线段树优化建图

思路分析

首先显然有一个 \(O(n\log^3n)\) 的大力树剖做法,但这个做法过于暴力,时间和空间都不允许,无法通过本题。

考虑优化这个做法,我们发现,对于每一个重链都在线段树上进行一次连边实在太过于暴力,时间复杂度高就来源于这里。

我们知道,一条重链是一颗树上独立的部分,我们可以为每一条重链预处理出一条路径,使得从这个点可以直接到达重链上的所有点。这样在树剖的时候对于每一个重链只需要连一条边就可以了。

那剩下的部分怎么办呢?不用怕,直接怼一个线段树优化建图上去就可以了,反正只有一个区间,对时间复杂度没有影响。

这样我们就得到了一个时间复杂度为 \(O(m\log^2n)\),空间复杂度为 \(O(n\log n)\) 的不那么暴力的做法,足以通过本题。

详细解释

上面的部分解释了一下大致思路,但还有亿些细节。

  • 如何预处理出重链路径?

对于每一个点,建立两个新的点,入点和出点,然后由这个点的入点向该点连边,该点向出点连边。

同时,自己的出点向自己的重儿子的出点连边,自己的重儿子的入点向自己的入点连边。这样就形成了两条路径,一条往下的出路径和一条往上的入路径。

  • 如何使用线段树优化建图?

跟正常的线段树优化建图差不多,只需要在树剖的配合下上树就行了。

struct STn{int l,r;};//没什么用的结构体
struct ST{
    STn a[P<<2];//开四倍
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;
        if(a[p].l==a[p].r){
            idt[p][0]=idt[p][1]=rnk[l];//rnk[l]才是对应的点,idt[p][0]是入出的节点编号,idt[p][1]是出树的
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);
        idt[p][0]=build_new_point();//动态开点,节约空间
        idt[p][1]=build_new_point();
        add(idt[p][0],idt[p<<1][0],0,0);//入树和出树连边
        add(idt[p][0],idt[p<<1|1][0],0,0);
        add(idt[p<<1][1],idt[p][1],0,0);
        add(idt[p<<1|1][1],idt[p][1],0,0);
    }
    void connect(int p,int point,int l,int r,int f){
        if(l<=a[p].l&&a[p].r<=r){
            if(f) add(point,idt[p][0],0,0);//f=1 表示点向区间连边
            else add(idt[p][1],point,0,0);//f=0 表示区间向点连边
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid) connect(p<<1,point,l,r,f);
        if(r>mid) connect(p<<1|1,point,l,r,f);
    }
}tree;

其他

然后就应该没什么大问题了,但是细节还是很多的。

  • 使用并查集维护 \(1\) 类边的连通。

  • 入点和出点,入树和出树不要搞混。

  • dfs 时只走树边。

  • 这题卡空间,建议使用邻接表存图。

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int N=2500000,P=50100;//n log n 空间
#define inf 0x3f3f3f3f

struct Edge{int v,w;};
vector <Edge> E[N];//邻接表存所有边
int to[P<<1],head[P],nxt[P<<1];//链星存树边
int dfn[P],rnk[P],dep[P],siz[P],son[P],fa[P],top[P];
int idx=1,n,m,in1,in2,in3,in4,in5,op,s;
int query_num,dfs_cnt,id;
int dis[N],vis[N],idt[P<<2][2];

int fat[P];
int find(int x){return fat[x]==x?x:fat[x]=find(fat[x]);}//并查集

int build_new_point(){//动态开点
    id++;return id;
}

void add(int u,int v,int c,int f){
    if(f==1){idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;}//f=1 表示这条边是树边
    E[u].push_back(Edge{v,c});
}

struct Query{
    int u1,v1,u2,v2,w;
}query[N];

struct Node{
    int x,dis;
}now;

bool operator < (Node a,Node b){
    return a.dis>b.dis;//大根堆
}

priority_queue <Node> q;

void Dijskra(){//最短路
    memset(dis,0x3f,sizeof dis);
    q.push(Node{s,0});dis[s]=0;
    while(!q.empty()){
        now=q.top();q.pop();
        if(vis[now.x]) continue;
        vis[now.x]=1;
        for(auto it:E[now.x]){
            int v=it.v;
            if(dis[v]<dis[now.x]+it.w) continue;
            dis[v]=dis[now.x]+it.w;
            q.push(Node{v,dis[v]});
        }
    }
}

void dfs_1(int s,int gr){//树剖预处理
    fa[s]=gr;dep[s]=dep[gr]+1;
    siz[s]=1;son[s]=-1;
    for(int i=head[s];i;i=nxt[i]){
        int v=to[i];
        if(v==gr) continue;
        dfs_1(v,s);
        siz[s]+=siz[v];
        if(son[s]==-1||siz[son[s]]<siz[v]) son[s]=v;
    }
}

void dfs_2(int s,int tp){
    top[s]=tp;
    dfn[s]=++dfs_cnt;
    rnk[dfs_cnt]=s;
    if(son[s]==-1) return ;
    add(son[s]+n,s+n,0,0);//入点往上
    add(s+2*n,son[s]+2*n,0,0);//出点往下
    dfs_2(son[s],tp);
    for(int i=head[s];i;i=nxt[i]){
        int v=to[i];
        if(v==son[s]||v==fa[s]) continue;
        dfs_2(v,v);
    }
}

struct STn{int l,r;};//没什么用的结构体
struct ST{
    STn a[P<<2];//开四倍
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;
        if(a[p].l==a[p].r){
            idt[p][0]=idt[p][1]=rnk[l];//rnk[l]才是对应的点,idt[p][0]是入出的节点编号,idt[p][1]是出树的
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);
        idt[p][0]=build_new_point();//动态开点,节约空间
        idt[p][1]=build_new_point();
        add(idt[p][0],idt[p<<1][0],0,0);//入树和出树连边
        add(idt[p][0],idt[p<<1|1][0],0,0);
        add(idt[p<<1][1],idt[p][1],0,0);
        add(idt[p<<1|1][1],idt[p][1],0,0);
    }
    void connect(int p,int point,int l,int r,int f){
        if(l<=a[p].l&&a[p].r<=r){
            if(f) add(point,idt[p][0],0,0);//f=1 表示点向区间连边
            else add(idt[p][1],point,0,0);//f=0 表示区间向点连边
            return ;
        }
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid) connect(p<<1,point,l,r,f);
        if(r>mid) connect(p<<1|1,point,l,r,f);
    }
}tree;

void add_edge_one_to_two(int point,int x,int y,int f){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        if(f) add(point,x+n,0,0);
        else add(x+2*n,point,0,0);//注意是 x 不是 top[x]
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    tree.connect(1,point,dfn[y],dfn[x],f);//剩下的部分用线段树
}

void add_edge_two_to_two(int query_id){
    int u1=query[query_id].u1,v1=query[query_id].v1;
    int u2=query[query_id].u2,v2=query[query_id].v2;
    int w=query[query_id].w;//把询问提取出来
    int uu=build_new_point(),vv=build_new_point();
    add(uu,vv,w,0);//建两个新的点并在这两点之间连有权值的边
    add_edge_one_to_two(vv,u2,v2,1);//出点向路径连边
    add_edge_one_to_two(uu,u1,v1,0);//路径向入点连边
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    id=3*n;//动态开点的编号从 3n 开始,n+1 到 2n 是入点,2n+1 到 3n 是出点
    for(int i=1;i<=n;i++) fat[i]=i;//不要忘了初始化
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d%d%d",&in1,&in2,&in3,&in4,&in5);
            if(find(in1)!=find(in2)||find(in3)!=find(in4)) continue;
            query[++query_num]=Query{in1,in2,in3,in4,in5};//保存一下询问
        }
        if(op==2){
            scanf("%d%d%d",&in1,&in2,&in3);
            if(find(in1)==find(in2)) continue;
            add(in1,in2,in3,1);add(in2,in1,in3,1);
            fat[find(in1)]=find(in2);
        }
    }
    for(int i=1;i<=n;i++)
        add(i+n,i,0,0),add(i,i+2*n,0,0);//先把出入点之间的边连上
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            dfs_1(i,0);
            dfs_2(i,i);
        }
    tree.build(1,1,n);//不要忘了建树
    for(int i=1;i<=query_num;i++)//连一下询问的边
        add_edge_two_to_two(i);
    Dijskra();
    for(int i=1;i<=n;i++) 
        if(dis[i]==inf) cout<<"-1 ";
        else cout<<dis[i]<<' ';
    cout<<'\n';
    return 0;
}

标签:重链,int,题解,类边,dis,入点,include,森林
From: https://www.cnblogs.com/TKXZ133/p/17458254.html

相关文章

  • OTOCI 题解
    OTOCI题目大意给定\(n\)个带权的点,需要进行四种操作:查询两点连通性;加边;修改点权;查询两点路径的权值和。思路分析首先观察题目,我们会发现,在所有的操作结束后,所有的点构成一个森林,这是因为题目中的加边是建立在两点不连通的基础上的,所以不会形成任何的环,到最后自然形成了一个......
  • Sell Pigs 题解
    SellPigs双倍经验题目大意有\(n\)个顾客前来买猪,共有\(m\)个猪圈,每个顾客携带着某一些猪圈的钥匙,需要买一定数量的猪。在顾客买完后,我们可以将打开的猪圈中的猪随意移动,移动完毕后所有的猪圈将关闭,直到下一个顾客到来时才能打开其拥有钥匙对应的猪圈。求最多能卖出多少猪......
  • 旅游 题解
    旅游题目大意对一颗树进行两种操作:将一条从\(u\)到\(v\)的链上的点的权值增加\(x\);查询从\(u\)到\(v\)的链上最大的\(p_i-p_j(dis_{ui}<dis_{uj})\),其中\(p_i\)表示点\(i\)的权值,\(dis_{AB}\)表示点\(A,B\)间唯一路径上边的数量。思路分析先思考,如果没有\(d......
  • Interesting Array 题解
    InterestingArray题目大意构造一个序列\(a\),使其满足若干限制条件,每个限制条件是形如lrq的式子,其意义是:\(\&_{i=l}^ra_i=q\)。题意分析看上去是构造题,实际上是数据结构题。我们不妨先令初始时\(a\)为一个全\(0\)序列,再逐一看每个限制条件。为了满足某一个限制条件......
  • Sum of MSLCM 题解
    SumofMSLCM题目大意定义\(\text{MSLCM}(n)\)为所有满足该数集的\(\text{lcm}\)为\(n\)的数集中元素个数最多的数集的所有数字的和,现有多次询问,求\[\sum_{i=2}^n\text{MSLCM}(i)\]思路分析大水题。虽然看着这个东西很可怕,但仔细一想你就会发现,其实\(\text{MSLCM}(n)......
  • Java模拟表单提交编码不同导致乱码问题解决
    最近有个业务需要模拟表单提交到asp页面中,但是我的项目编码是UTF8,而asp页面是GB2312,中文字段提交后,到达数据库后是乱码.问题的解决在于模拟提交的时候指定编码:我用的HTTP框架是Unirest,代码如下:......
  • 安装Navicat遇到的问题解决
    1、如果遇到安装出现问题,并且不能激活,需要重新卸载安装。需要彻底卸载2、除了点击卸载安装之后,需要注册表删除掉所有的信息,以及删除掉在C:\ProgramFiles\PremiumSoft的Navicat删除掉3、删除注册表Win+R之后输入:regedit进入注册表3.1找到计算机\HKEY_CURRENT_USER\Softwar......
  • [ABC208E] Digit Products 题解
    DigitProducts题目大意求有多少个不大于\(n\)的正整数,使得该正整数各位乘积不大于\(k\)。思路分析观察数据范围,首先考虑数位DP。考虑设计记忆化搜索函数dfs(intpos,boollimit,boollead0,intmul)表示当前枚举到第\(\text{pos}\)位,第\(\text{pos}\)位是否受到限......
  • [ABC207E] Mod i 题解
    Modi题目大意给定一个序列\(a\),问将其划分成若干段,满足第\(i\)段的和是\(i\)的倍数的划分方案的个数。思路分析考虑DP,设\(f_{i,j}\)表示将序列中前\(i\)个数划分成\(j\)段,且满足条件的划分方案的个数,容易得出状态转移方程:\[f_{i,j}=\sumf_{k,j-1}(\sum_{h=k+1}......
  • [ABC205E] White and Black Balls 题解
    WhiteandBlackBalls题目大意将\(n\)个白球,\(m\)个黑球排成一列,要求满足\(\foralli\in[1,n+m],w_i\leb_i+k\),问存在多少种排法。其中\(w_i\)表示第\(i\)个球前的白球数量,\(b_i\)表示第\(i\)个球前的黑球数量。思路分析我们可以将一种排法映射成一条从\((0,0)......