DS線段樹優化最短路&&01bfs淺談

• 2021 年 3 月 1 日
• 筆記
• 圖論, 算法精講

1簡介

為什麼需要？原因很簡單，當需要有大量的邊去連時，用線段樹優化可以直接用點連向區間，或從區間連向點，或從區間連向區間，如果普通連邊，複雜度是不可比擬的。下面簡單講解一下線段樹（ST）優化建圖。

2講解

2.1 兩棵樹

線段樹優化建圖需要兩棵樹：入樹和出樹，入樹指被點或區間指向的樹，連邊時從結點或邊連向入樹，出樹指連向點或結點的邊的樹，連邊時連向點或結點。入樹之間的邊是父親指向兒子，出樹之間的邊是兒子指向父親，如果結點個數為n，我們通常用k表示第一顆線段樹，k+4*n表示第二顆線段樹，k+8*n表示普通結點（為什麼要有普通結點一會說），這樣，實際上給每顆線段樹都留了4*n個結點。

上面的三張圖分別是出樹，入樹和連結點時的樣子。

為什麼要這麼做，可以這麼想，出樹保證的是所有的兒子結點都能走到他們父親結點連向的邊，

所有的兒子結點都能被兩項他們父親節點的邊走到，所以不難理解為什麼出樹和入樹的父親結點與兒子結點之間的邊這樣建。

2.2 建樹

這個過程其實與我們普通線段樹的建法一樣，只不過多了一個步驟加邊，同時，如果當前結點已經是葉子結點，還需要一步操作，及新建一個綠色結點，把每棵樹的子結點向對應綠色結點連一條 無向邊，如圖（藍色邊）：

代碼：

inline void build(ll k,ll l,ll r){
	if(l==r){
		add(k,l+8*n,0);add(l+8*n,k,0);
		add(k+4*n,l+8*n,0);add(l+8*n,k+4*n,0);
		return;
	}
	add(k,k*2,0);add(k,k*2+1,0);
	add(k*2+4*n,k+4*n,0);add(k*2+1+4*n,k+4*n,0);
	ll mid=l+r>>1;
	build(k*2,l,mid);build(k*2+1,mid+1,r);
}

實際上，我們建綠色結點是為了方便我們連點對區間邊，比如上圖，同時也給了一個點連到區間的例子。所以，如果沒有點對區間的連邊，這個過程可以省略。（但是為了好理解，博主一般打上）

2.3 鄰接表

這個地方只放代碼，不知道的請參考其他博客

struct edge{
	ll next,to,w;
	inline void intt(ll to_,ll next_,ll w_){
		next=next_;to=to_;w=w_;
	}
};
edge li[M];ll head[N],tail;

inline void add(ll from,ll to,ll w){
	li[++tail].intt(to,head[from],w);
	head[from]=tail;
}

2.4 加邊

這個地方只講解點與區間相連，事實上，如果是區間與區間想連的話，可以通過加一個虛擬結點來實現，如下：

註：虛擬結點之間的邊帶權值，其餘邊權值為0。

這裡的加邊和我們對普通線段樹的操作大同小異。只需要注意邊的方向就行了：

inline void addh(ll k,ll z,ll y,ll pd,ll u,ll w){
	ll l=p[k].l,r=p[k].r,mid=l+r>>1;
	if(l==z&&y==r){
		if(!pd) return add(u+8*n,k,w);
		else return add(k+4*n,u+8*n,w);
	}
	if(y<=mid) addh(k*2,z,y,pd,u,w);
	else if(z>mid) addh(k*2+1,z,y,pd,u,w);
	else addh(k*2,z,mid,pd,u,w),addh(k*2+1,mid+1,y,pd,u,w);
}

代碼里的pd是用來判斷是邊連向區間還是從區間連向邊。

註：只有線段樹上的點連到綠色結點時才帶邊權，如2.2那個圖，只有綠色邊帶權值。

2.5 跑最短路

事實上可以跑dij，如果是只有0邊權和1邊權建議跑01bfs，因為01bfs的複雜度是\(O(n)\)

現在放01bfs的代碼如下，想看dij代碼的可以去本博客存的最短路代碼中去看:

deque<ll> q;ll d[N];
bool vis[N];

inline void bfs(ll s){
	memset(d,INF,sizeof(d));
	q.push_front(s);d[s]=0;
	while(q.size()){
		ll top=q.front();q.pop_front();
		if(vis[top]) continue;
		vis[top]=1;
		for(ll k=head[top];k;k=li[k].next){
			ll to=li[k].to;
			if(vis[to]) continue;
			if(d[to]>d[top]+li[k].w){
				d[to]=d[top]+li[k].w;
				if(li[k].w) q.push_back(to);
				else q.push_front(to);
			}
		}
	}
}

01bfs的思想其實就是貪心，實現方法雙端隊列，0邊權加到隊首，1邊權加到隊尾，這樣從隊頭取結點能保證它經過了較多的0邊。其餘與普通bfs無異。

2.6注意事項

1. 注意在有點到區間連線時才必須要綠色節點，其餘情況綠色節點不必要。
2. 在區間與區間連線時我們使用了虛擬節點，事實上直接區間連區間也未嘗不可，但是我們習慣上操作還是喜歡用區間連向點，這樣只需要寫一個函數，方便操作。
3. 在題目要求要無向邊時（即雙向邊），出樹和入樹父親結點與兒子結點之間邊的方向不變，若點連向區間時直接操作即可，例如從區間a到點b，參照2.2的圖即可，但是如果是區間連向區間，需要建虛擬結點的話，還是應當多建虛擬節點，不能用原有虛擬節點去連雙向邊。例如，區間a到區間b連無向邊，從a連向b需要建立兩個虛擬結點，從b再連向a需要再建立兩個虛擬節點，否則，會出現原來題目中沒有出現的邊，導致最短路出錯。切忌！

3例題

3.1 洛谷CF786B

//www.luogu.com.cn/problem/CF786B

裸題，連完邊跑dij即可。具體實現如下：

代碼：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 900010
#define M 9000090
using namespace std;

const ll INF=0x3f3f3f3f;

struct edge{
	ll to,next,w;
	inline void intt(ll to_,ll next_,ll w_){
		to=to_;next=next_;w=w_;
	}
};
edge li[M];ll head[N],tail;

inline void add(ll from,ll to,ll w){
	li[++tail].intt(to,head[from],w);
	head[from]=tail;
}

ll n,q,s;

struct rode{
	ll l,r;
};
rode p[N];

inline void build(ll k,ll l,ll r){
	p[k].l=l;p[k].r=r;
	if(l==r){
		add(l+8*n,k,0);add(k+4*n,l+8*n,0);
		add(k,l+8*n,0);add(l+8*n,k+4*n,0);
		return;
	}
	add(k,k*2,0);add(k*2+n*4,k+n*4,0);
	add(k,k*2+1,0);add(k*2+1+n*4,k+n*4,0);
	ll mid=l+r>>1;
	build(k*2,l,mid);build(k*2+1,mid+1,r);
}

inline void addh(ll k,ll z,ll y,ll pd,ll u,ll w){
	ll l=p[k].l,r=p[k].r,mid=l+r>>1;
	if(l==z&&y==r){
		if(!pd) return add(u+8*n,k,w);
		else return add(k+4*n,u+8*n,w);
	}
	if(y<=mid) addh(k*2,z,y,pd,u,w);
	else if(z>mid) addh(k*2+1,z,y,pd,u,w);
	else addh(k*2,z,mid,pd,u,w),addh(k*2+1,mid+1,y,pd,u,w);
}

struct DIJ{
	ll d[N];bool vis[N];
	
	struct node{
		ll to,w;
		node() {}
		node(ll to,ll w) : to(to),w(w) {}
	};
	
	struct cmp{
		inline bool operator () (node a,node b){
			return a.w>b.w;
		}
	};
	
	priority_queue<node,vector<node>,cmp> q;
	
	inline void Dij(ll s){
		memset(d,INF,sizeof(d)); d[s]=0;
		q.push(node(s,0));
		while(!q.empty()){
			node fr=q.top();q.pop();
			if(vis[fr.to]) continue;
			vis[fr.to]=1;
			for(int k=head[fr.to];k;k=li[k].next){
				ll to=li[k].to;
				if(!vis[to]&&d[to]>d[fr.to]+li[k].w){
					d[to]=d[fr.to]+li[k].w;
					q.push(node(to,d[to]));
				}
			}
		}
	}
};

DIJ dij;

int main(){
	scanf("%lld%lld%lld",&n,&q,&s);
	build(1,1,n);
	for(ll i=1;i<=q;i++){
		ll op,v,u,w,l,r;
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld%lld",&v,&u,&w);
			add(v+8*n,u+8*n,w);
		}
		else if(op==2){
			scanf("%lld%lld%lld%lld",&v,&l,&r,&w);
			addh(1,l,r,0,v,w);
		}
		else if(op==3){
			scanf("%lld%lld%lld%lld",&v,&l,&r,&w);
			addh(1,l,r,1,v,w);
		}
	}
	s+=8*n;
	dij.Dij(s);
	for(int i=1;i<=n;i++){
		printf("%lld ",dij.d[i+8*n]<=4e18?dij.d[i+8*n]:-1);
	}
	
	return 0;
}

3.2 洛谷P6348

是區間連向區間的例題，注意虛擬節點不能亂用即可，虛擬節點的編號為k+9*n。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 9000100
#define M 10001000
using namespace std;

const ll INF=0x3f3f3f3f;

struct edge{
	ll next,to,w;
	inline void intt(ll to_,ll next_,ll w_){
		next=next_;to=to_;w=w_;
	}
};
edge li[M];ll head[N],tail;

inline void add(ll from,ll to,ll w){
	li[++tail].intt(to,head[from],w);
	head[from]=tail;
}

ll p[N],n,m,s;

inline void build(ll k,ll l,ll r){
	if(l==r){
		add(k,l+8*n,0);add(l+8*n,k,0);
		add(k+4*n,l+8*n,0);add(l+8*n,k+4*n,0);
		return;
	}
	add(k,k*2,0);add(k,k*2+1,0);
	add(k*2+4*n,k+4*n,0);add(k*2+1+4*n,k+4*n,0);
	ll mid=l+r>>1;
	build(k*2,l,mid);build(k*2+1,mid+1,r);
}

inline void addh(ll k,ll l,ll r,ll z,ll y,ll pd,ll u,ll w){
	if(l==z&&r==y){
		if(!pd) return add(u,k,w);
		else return add(k+4*n,u,w);
	}
	ll mid=l+r>>1;
	if(y<=mid) addh(k*2,l,mid,z,y,pd,u,w);
	else if(z>mid) addh(k*2+1,mid+1,r,z,y,pd,u,w);
	else addh(k*2,l,mid,z,mid,pd,u,w),addh(k*2+1,mid+1,r,mid+1,y,pd,u,w);
}

deque<ll> q;ll d[N];
bool vis[N];

inline void dfs(ll s){
	memset(d,INF,sizeof(d));
	q.push_front(s);d[s]=0;
	while(q.size()){
		ll top=q.front();q.pop_front();
		if(vis[top]) continue;
		vis[top]=1;
		for(ll k=head[top];k;k=li[k].next){
			ll to=li[k].to;
			if(vis[to]) continue;
			if(d[to]>d[top]+li[k].w){
				d[to]=d[top]+li[k].w;
				if(li[k].w) q.push_back(to);
				else q.push_front(to);
			}
		}
	}
}

int main(){
	scanf("%lld%lld%lld",&n,&m,&s);
	build(1,1,n);
	ll tailx=9*n;
	for(ll i=1;i<=m;i++){
		ll a,b,c,dd;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&dd);
		addh(1,1,n,a,b,1,++tailx,0);
		addh(1,1,n,c,dd,0,++tailx,0);
		add(tailx-1,tailx,1);
		addh(1,1,n,c,dd,1,++tailx,0);
		addh(1,1,n,a,b,0,++tailx,0);
		add(tailx-1,tailx,1);
	}
	dfs(s+8*n);
	for(ll i=1;i<=n;i++) printf("%lld\n",d[i+8*n]);
	return 0;
}

這裡在附上引用中大佬的代碼，他的代碼中沒有綠色節點。

int n,m,s,id[N],cnt;

struct Node {int l,r;}t[N];
void build(int p,int l,int r) {
    t[p].l=l, t[p].r=r;
    if(l==r) {
        id[l]=p;
        return;
    }
    add(p,p*2,0), add(p*2+n*4,p+n*4,0);
    add(p,p*2+1,0), add(p*2+1+n*4,p+n*4,0);
    build(p*2,l,(l+r)/2), build(p*2+1,(l+r)/2+1,r);
}
void adds(int p,int x,int y,bool type,int u) {
    int l=t[p].l, r=t[p].r, mid=((l+r)>>1);
    if(l==x&&y==r) {
        if(!type) return add(u,p,0);
        else return add(p+4*n,u,0);
    }
    if(y<=mid) adds(p*2,x,y,type,u);
    else if(x>mid) adds(p*2+1,x,y,type,u);
    else adds(p*2,x,mid,type,u), adds(p*2+1,mid+1,y,type,u);
}

int d[N];
void bfs() {
    deque<int>q; q.push_front(s);
    memset(d,0x3f,sizeof(d)); d[s]=0;
    while(!q.empty()) {
        int u=q.front(); q.pop_front();
        for(int i=hd[u],v;i;i=e[i].nxt)
            if(d[v=e[i].to]>d[u]+e[i].w) {
                d[v]=d[u]+e[i].w;
                if(!e[i].w) q.push_front(v);
                else q.push_back(v);
            }
    }
}

signed main() {
    scanf("%d%d%d",&n,&m,&s);
    build(1,1,n);
    cnt=8*n;
    for(int i=1,a,b,c,dd;i<=m;i++) {
        scanf("%d%d%d%d",&a,&b,&c,&dd);
        int x=++cnt, y=++cnt;
        add(y,x,1), adds(1,c,dd,0,x), adds(1,a,b,1,y);
        x=++cnt, y=++cnt;
        add(y,x,1), adds(1,a,b,0,x), adds(1,c,dd,1,y);
    }
    for(int i=1;i<=n;i++) add(id[i],id[i]+4*n,0), add(id[i]+4*n,id[i],0);
    s=id[s]+4*n;
    bfs();
    for(int i=1;i<=n;i++) printf("%d\n",d[id[i]]);
    return 0;
}

引用：

//www.luogu.com.cn/blog/forever-captain/DS-optimize-graph

更新日誌