最短路之分层图

yuanheci 2023年04月05日 530次浏览

  分层图最短路是指在可以进行分层图的图上解决最短路问题。分层图：可以理解为有多个平行的图。

  一般模型是：在一个正常的图上可以进行 kk 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。

分层图有两种建法：

  (1)(1) 实实在在的建图，n+1n + 1层。

  (2)(2) 逻辑上的对图分层，一般就是给distdist数组或者stst数组，总之就是你需要参与求解实际问题的数据结构额外增加一维数组来模拟nn层的效果。（感觉更好写）

  个人感觉分层图一般用在最短路有一些条件的时候，对应到DP的考虑就是需要多开一维的情况。

  分层图的思想也是一种 “拆点” 的思想，即将每个原始点拆成第二维不同的若干个点，然后再求解。

《通信线路》

  一种做法是二分 + 双端队列优化，或者也可以用分层图来做。

分层图思路：

  注意求的是最大的需要支付的边权花费的最小值，不是总和！

  令 dist[x][p]dist[x][p] 表示从 11 走到 xx，且花费了 pp 次报销机会的方案的集合中最大边权的最小值。

考虑一条边 (x,y,z)(x,y,z) 对 dpdp 的贡献：

  • 若在这条边不使用机会：f[y,p]=min(f[y,p],max(f[x,p],z))f[y, p] = min(f[y, p], max(f[x, p], z))

  • 若在这条边使用机会：f[y,p+1]=min(f[y,p+1],f[x,p])f[y, p+1] = min(f[y, p+1], f[x, p])

AC代码：

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int dist[N][N];    //dist和st开成二维
bool st[N][N];
PII q[N * N];
int n, m, k; 
int ans;

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(){
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	int hh = 0, tt = 0;
	q[tt++] = {1, 0};
	dist[1][0] = 0;
	st[1][0] = true;
	while(hh != tt){
		auto t = q[hh++];
		if(hh == N * N) hh = 0;
		int x = t.x, cnt = t.y;
		st[x][cnt] = false;
		for(int i = h[x]; ~i; i = ne[i]){
			int j = e[i];
			//不报销 
			if(dist[j][cnt] > max(dist[x][cnt], w[i])){
				dist[j][cnt] = max(dist[x][cnt], w[i]);
				if(!st[j][cnt]){
					st[j][cnt] = true;
					q[tt++] = {j, cnt};
					if(tt == N * N) tt = 0;
				}
			} 
			//报销
			if(cnt + 1 <= k && dist[j][1 + cnt] > dist[x][cnt]){
				dist[j][1 + cnt] = dist[x][cnt];
				if(!st[j][1 + cnt]){
					st[j][1 + cnt] = true;
					q[tt++] = {j, 1 + cnt};
					if(tt == N * N) tt = 0;
				} 
			} 
		}		
	} 
}

void solve(){
	scanf("%d%d%d", &n, &m, &k);
	memset(h, -1, sizeof h);
	for(int i = 1; i <= m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c), add(b, a, c);
	}
	spfa();
	ans = INF;
	for(int i = 0; i <= k; i++) ans = min(ans, dist[n][i]);
	if(ans == INF) puts("-1");
	else printf("%d\n", ans);
}

int main(){
	int _ = 1;
//	scanf("%d", &_);
	while( _ -- ){
		solve();
	}
	return 0;
}

《飞行路线》

本题求的就是总和最小了。

SPFA

本题卡了一手SPFA，有一个数据会TLE，果然SPFA已死

/**
	SPFA貌似被卡了一个数据，T了 
*/

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 10010, M = 50010, INF = 0x3f3f3f3f;
int h[N], e[M * 2], ne[M * 2], w[M * 2], idx;
int dist[N][12];
bool st[N][12];
int n, m, k;
int s, t;
PII q[N * 12];
int hh, tt;

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(){
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	hh = 0, tt = 0;
	q[tt++] = {s, 0};
	dist[s][0] = 0;
	st[s][0] = true;
	while(hh != tt){
		auto t = q[hh++];
		if(hh == N * 12) hh = 0;
		int x = t.x, cnt = t.y;
		st[x][cnt] = false;
		for(int i = h[x]; ~i; i = ne[i]){
			int j = e[i];
			//不报销 
			if(dist[j][cnt] > dist[x][cnt] + w[i]){
				dist[j][cnt] = dist[x][cnt] + w[i];
				if(!st[j][cnt]){
					st[j][cnt] = true;
					q[tt++] = {j, cnt};
					if(tt == N * 12) tt = 0; 
				}
			}
			//报销
			if(1 + cnt <= k && dist[j][1 + cnt] > dist[x][cnt]){
				dist[j][1 + cnt] = dist[x][cnt];
				if(!st[j][1 + cnt]){
					st[j][1 + cnt] = true;
					q[tt++] = {j, 1 + cnt};
					if(tt == N * 12) tt = 0;
				}
			} 
		}
	}
}

void solve(){
	scanf("%d%d%d", &n, &m, &k);
	scanf("%d%d", &s, &t);
	memset(h, -1, sizeof h);
	for(int i = 1; i <= m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c), add(b, a, c);
	}
	spfa();
	int ans = INF;
	for(int i = 0; i <= k; i++) ans = min(ans, dist[t][i]);
	printf("%d\n", ans);
}

int main(){
	int _ = 1;
//	scanf("%d", &_);
	while(_ -- ){
		solve();
	}
	return 0;
}

Dijkstra

/**
	Dijkstra 
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = 50010, INF = 0x3f3f3f3f;
int h[N], e[M * 2], ne[M * 2], w[M * 2], idx;
int dist[N][12];
bool st[N][12];
int n, m, k;
int s, t;

struct Node{
	int d, id, c;
	bool operator> (const Node& t) const{
		return d > t.d;
	}
};

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
	priority_queue<Node, vector<Node>, greater<Node>> heap;
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	dist[s][0] = 0;
	heap.push({0, s, 0});
	while(heap.size()){
		auto t = heap.top();
		heap.pop();
		int id = t.id, cnt = t.c, d = t.d;
		if(st[id][cnt]) continue;
		st[id][cnt] = true;  //第一次出队时确定 
		for(int i = h[id]; ~i; i = ne[i]){
			int j = e[i];
			//不报销 
			if(dist[j][cnt] > d + w[i]){
				dist[j][cnt] = d + w[i];
				heap.push({dist[j][cnt], j, cnt});
			}
			if(1 + cnt <= k && dist[j][1 + cnt] > d){
				dist[j][1 + cnt] = d;
				heap.push({dist[j][1 + cnt], j, 1 + cnt});
			}
		}
	}
}

void solve(){
	scanf("%d%d%d", &n, &m, &k);
	scanf("%d%d", &s, &t);
	memset(h, -1, sizeof h);
	for(int i = 1; i <= m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c), add(b, a, c);
	}
	dijkstra();
	int ans = INF;
	for(int i = 0; i <= k; i++) ans = min(ans, dist[t][i]);
	printf("%d\n", ans);
}


int main(){
	int _ = 1;
	//scanf("%d", &_);
	while(_ -- ){
		solve();
	} 
	return 0;	
}
上一篇： 进制转换