k 短路

Posted on Edited on In

k 短路

好像是一个比较简单的东西

对于 正权有向图，\(\displaystyle G=(V,E),V=\{V_i\}_{i=1}^nE=\{(u_i,v_i,w_i)\}_{i=1}^m\)，求 \(s\) 到 \(t\) 的前 \(k\) 短路。

考虑建立反图 \(G'=(V,E')\)，容易 \(\text{Dijkstra}\) 求得 \(t\) 的单源最短路 \(dis_i\)，并且建立一棵最短路树。

考虑 \(s\rightarrow t\) 的最短路，一定是走了一些树边和非树边。

选择一条非树边 \((u,v,w)\) 会使长度增加 \(w'=w-(dis_u-dis_v)\)，称 \(w'\) 为额外长度。

考虑我们选择的非树边序列 \((u_i,v_i,w_i)\)，显然有：\(u_{i+1}\) 是 \(v_i\) 在最短路树上的祖先。

考虑用搜索扩展的方式来遍历所有路径情况。

记录当前的节点 \(u\)，产生的额外长度 \(d\)，则每次的扩展可以归纳为。

  1. 从 \(u\) 所有祖先中取出边的集合 \(S_u\)。

  2. 依次遍历 \(S_u\) 中的所有边 \((u_i,v_i,w'_i)\)，进入递归 \(u'=v_i,d'=d+w'_i\).

每次扩展会产生一个新的状态，且恰好可以遍历每一个状态一次.


然而，为了求出前 \(k\) 短路，我们必须按照答案从小到大遍历。

那么我们首先需要将集合 \(S_u\) 排序，从小到大遍历，其次要对于不同的递归情况按照大小扩展。

容易想到用一个堆维护扩展的顺序，为了保存遍历 \(S_u\) 集合的过程，记录一个指针 \(p\)。

此时，用堆维护扩展的方法显然：

  1. 取出堆顶状态 \((u,d,p)\)，

  2. 转移：

    1. 在当前递归栈中移动 \(p\leftarrow p+1\)，改变 \(d\)，

    2. 模拟上面，建立新的递归栈，同时令指针为\(0\)。

得到 \(u'=v_{u,p},d'=d+w'_{v,0},p'=0\)。

如果暴力处理出 \(S_u\)，则预处理复杂度为 \(O(nm\log m)\)，状态扩展复杂度为 \(O(2k\log k)\)。

用可持久化可并堆处理 \(S_u\)，\(p\) 记录当前堆顶节点指针。

每次扩展 \(p\leftarrow lson_p\) 或者 \(p\leftarrow rson_p\)，增加一个扩展状态。

则预处理复杂度以及空间复杂度为\(O(m\log m)\)，状态扩展复杂度为 \(O(3k\log k)\)。

Luogu P2483

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

const int N=5010,M=2e5+10;
const db eps=1e-7,INF=1e18;

template <class T> class Heap{
public:
	T val;
	int h;
	Heap *ls,*rs;
	T top(){ return val; }
	Heap(){}
	Heap(Heap *x):val(x->val),h(x->h),ls(x->ls),rs(x->rs){ ; }
	Heap(T val):val(val),h(0),ls(0),rs(0){ ; }
	friend Heap* Union(Heap *x,Heap *y){
		if(!x) return y;
		if(!y) return x;
		if(y->val<x->val) swap(x,y);
		Heap* u=new Heap(x);
		u->rs=Union(u->rs,y);
		if(u->rs && (!u->ls || u->rs->h>u->ls->h)) swap(u->ls,u->rs);
		u->h=u->rs?u->rs->h+1:1;
		return u;
	}
	Heap* pop(){ return Union(ls,rs); }
	friend Heap* push(Heap *u,T val){ return Union(u,new Heap(val)); }
};
typedef Heap <Pair> Node;
Node *rt[N];

struct Edge{
	int to;db w;
	Edge *nxt;
	Edge(){}
	Edge(int to,db w,Edge* nxt):to(to),w(w),nxt(nxt){ ; }
};
Edge *head[N],*pre[N];
void AddEdge(int u,int v,db w){
	Edge* t=new Edge(v,w,head[u]);
	head[u]=t;
}
int n,m,fa[N];
db E,dis[N];

void Dijkstra(int u){
	static priority_queue <Pair,vector<Pair>,greater<Pair>> que;
	rep(i,1,n) dis[i]=INF;
	dis[u]=0,que.push({0,u});
	while(!que.empty()){
		int u=que.top().se;db d=que.top().fi; que.pop();
		if(dis[u]<d-eps) continue;
		for(Edge *i=head[u];i;i=i->nxt) {
			int v=i->to;
			if(dis[v]>dis[u]+i->w+eps) pre[v]=i,fa[v]=u,que.push({dis[v]=dis[u]+i->w,v});
		}
	}
}

void Construct(){
	static int I[N];
	rep(i,1,n) I[i]=i;
	sort(I+1,I+n+1,[&](int x,int y){ return dis[x]<dis[y]; });
	rep(u,1,n) {
		for(Edge *i=head[u];i;i=i->nxt) {
			int v=i->to;
			if(pre[v]==i) continue;
			rt[v]=push(rt[v],mp(i->w-(dis[v]-dis[u]),u));
		}
	}
	rt[n]=0;
	rep(j,1,n) {
		int u=I[j];
		rt[u]=Union(rt[u],rt[fa[u]]);
	}
}

struct State{
	db s;
	Node *rt;
	bool operator < (const State &__) const {
		return s>__.s;
	}
};

int ans;
void Kth_Path(){
	static priority_queue <State> que;
	if(dis[1]>E+eps) return void(puts("0"));
	ans=1,E-=dis[1];
	if(rt[1]) que.push({dis[1]+rt[1]->val.fi,rt[1]});
	while(!que.empty()) {
		State u=que.top(); que.pop();
		if(u.s>E+eps) break;
		int v=u.rt->val.se;
		ans++,E-=u.s;
		if(rt[v]) que.push({u.s+rt[v]->top().fi,rt[v]});
		u.s-=u.rt->val.fi;
		if(u.rt->ls) {
			Pair w=u.rt->ls->val;
			que.push({u.s+w.fi,u.rt->ls});
		}
		if(u.rt->rs) {
			Pair w=u.rt->rs->val;
			que.push({u.s+w.fi,u.rt->rs});
		}
	}
	printf("%d\n",ans);
}

int main(){
	n=rd(),m=rd(),scanf("%lf",&E);
	rep(i,1,m){
		int u=rd(),v=rd();db w; scanf("%lf",&w);
		AddEdge(v,u,w);
	}
	Dijkstra(n);
	Construct();
	Kth_Path();
}