左偏树

notes

概述

二叉堆额外维护一个 $dis$，表示到空节点的最短长度，保证 $dis_{lc} > dis_{rc}$ 即可保证根节点的 $dis$ 为 $O(\log n)$。

合并时跳右儿子即可，时间复杂度 $O(\log n)$。

1.【模板】左偏树/可并堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+100;
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,a[N];

#define lc(x) (t[x].ls)
#define rc(x) (t[x].rs)
struct TREE{ int ls,rs,dis,fa,v; }t[N];
int find(int x){ return t[x].fa==x?x:t[x].fa=find(t[x].fa); }
int mer(int x,int y){
	if(!x||!y) return x^y;
	if(t[x].v>t[y].v||(t[x].v==t[y].v&&x>y)) swap(x,y);
	rc(x)=mer(rc(x),y);
	if(t[lc(x)].dis<t[rc(x)].dis) swap(lc(x),rc(x));
	t[x].dis=t[rc(x)].dis+1,t[lc(x)].fa=t[rc(x)].fa=x;
	return x;
}
void del(int x){ t[x].v=-1,t[lc(x)].fa=lc(x),t[rc(x)].fa=rc(x),t[x].fa=mer(lc(x),rc(x)); }
#undef lc(x)
#undef rc(x)

int main(){
	
	n=rd,m=rd;
	for(int i=1;i<=n;++i) t[i]={0,0,0,i,rd};
	
	for(int i=1,op,x,y;i<=m;++i){
		op=rd,x=rd; if(op==1) y=rd;
		if(op==1){
			if(t[x].v==-1||t[y].v==-1) continue;
			x=find(x),y=find(y);
			if(x!=y) t[x].fa=t[y].fa=mer(x,y);
		}
		else{
			if(t[x].v==-1) printf("-1\n");
			else x=find(x),printf("%d\n", t[x].v),del(x);
		}
	}
	
	return 0;
}

【模板】k 短路 / [SDOI2010] 魔法猪学院

最优策略是，每次找到一条未考虑的最短路径。

以 $n$ 为根建出反图的最短路树。

对于不在树上的边 $e: (u \to v,w)$，记 $\delta(e) = dis_v+w-dis_u$。

对于一条 $1 \to n$ 路径，记 $S$ 为路径上不在最短树上的边的集合，那么路径长度为 $dis_1 + \sum_{e \in S} \delta(e)$。

$dis_1$ 是定值，只需求出后面的未出现的最小值即可。

将边的顺序钦定好，此时边的集合唯一对应一条 $1 \to n$ 的路径。

考虑动态加边，那么每次会将最后一条边换掉，或者加一条新边。

考虑对每个点维护一个边集，存以其到 $n$ 链上为起点的非树边。

用堆维护，每次相当于向下移动一步。

初始化时需要继承之前的信息，用可持久化堆。

时间复杂度 $O(n\log n+m\log m+V\log V)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;

using db=double;
#define pid pair<int,db>
#define fi first
#define se second
#define pb push_back
#define U(x) ((int)x.size())
const int N=5e4+100,M=2e5+100;
const db INF=1e15,eps=1e-8;
inline int sgn(db x){ return (x>eps)-(x<-eps); }
inline int chkmin(db &x,db y){ return sgn(y-x)<0?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,fa[N],pre[M]; db E;
struct ADJ{ int v; db w; int i; };
vector<ADJ> G[N],R[N];

struct cmp{ bool operator()(const pid &x,const pid &y){ return sgn(x.se-y.se)>0; } };
priority_queue<pid,vector<pid>,cmp> q; int vis[N]; db dis[N];
void dij(){
	for(int i=1;i<=n;++i) vis[i]=0,dis[i]=INF; q.push({n,dis[n]=0});
    while(!q.empty()){
        int u=q.top().fi; q.pop(); if(vis[u]) continue; vis[u]=1;
        for(auto [v,w,i]:R[u]) if(chkmin(dis[v],dis[u]+w)) fa[v]=u,pre[v]=i,q.push({v,dis[v]});
    }
}

namespace HEAP{
	#define lc(x) (t[(x)].ls)
	#define rc(x) (t[(x)].rs)
	#define v(x) (t[(x)].v)
	#define dis(x) (t[(x)].dis)
	#define to(x) (t[(x)].to)
    struct TREE{ int ls,rs,dis,to; db v; }t[N<<5]; int tot=0;
    
    inline int make(int to,db v){ return t[++tot]={0,0,1,to,v},tot; }
    inline int clone(int x){ return t[++tot]=t[x],tot; }
    int mer(int x,int y){
		if(!x||!y) return x^y;
		if(v(x)>v(y)) swap(x,y);
		int z=clone(x); rc(z)=mer(rc(z),y);
		if(t[lc(z)].dis<(t[rc(z)].dis)) swap(lc(z),rc(z));
		dis(z)=(t[rc(z)].dis)+1; return z;
    }
};
int rt[N];

void init(){
    using namespace HEAP;
    for(int i=1;i<=n;++i) q.push({i,dis[i]});
    while(!q.empty()){
        int u=q.top().fi; q.pop();
        for(auto [v,w,i]:G[u]) if(pre[u]!=i) rt[u]=mer(rt[u],make(v,dis[v]-dis[u]+w));
        rt[u]=mer(rt[u],rt[fa[u]]);
    }
}

int calc(){
	using namespace HEAP;
    if(sgn(dis[1]-E)>0) return 0;
    E-=dis[1]; int res=1;
	if(!rt[1]) return res;
    q.push({rt[1],v(rt[1])});
    while(!q.empty()){
    	auto [u,d]=q.top(); q.pop();
    	if(sgn(dis[1]+d-E)>0) break;
    	E-=dis[1]+d,++res;
    	if(lc(u)) q.push({lc(u),d-v(u)+v(lc(u))});
    	if(rc(u)) q.push({rc(u),d-v(u)+v(rc(u))});
    	if(rt[to(u)]) q.push({rt[to(u)],d+v(rt[to(u)])});
	}
    return res;
}

int main(){
	
	n=rd,m=rd,scanf("%lf", &E);
    for(int i=1,u,v;i<=m;++i){
        u=rd,v=rd; db w; scanf("%lf", &w);
        if(u==n) continue;
        G[u].pb({v,w,i}),R[v].pb({u,w,i});
    }
    for(int u=1;u<=n;++u) reverse(G[u].begin(),G[u].end()),reverse(R[u].begin(),R[u].end());
    
    dij(),init();
    
	printf("%d\n", calc());

    return 0;
}

参考

可合并堆

k 短路