图论之分层图最短路总结与经典例题

爱被打了一巴掌 2022-12-01 01:17 67阅读 0赞

#### 一、分层图 ####

分层图只是**建图**时有区别，但跑最短路板子都是一样的，正所谓图论最难的就是建图，只要有合适的建图方法，那么问题就很简单了。

分层图是指有很多个平行的图，各个平行的图之间有特殊的连接边。

如何更好的理解分层图呢，就想一下我们平时坐的地铁，地铁的某一条线就是一层图，有三条线就相当于有三层平行的图，每层之间通过共有的地铁站连接起来。这就是分层图。

**用分层图的几种情况：**  
**1、** 有k个不同集合的边，将每个集合内的边建成一张图，再建立第k+1个图，是一个虚层，用这个虚层将这k张图连接起来。每次可以通过虚层转移到另一个集合的图中。如例1.小雨坐地铁。  
**2、** 有k个机会使得走当前此边不花费代价或花费特殊的代价，可以建立k张相同的该图，每张图之间用有边的点连接起来，其代价是0或是特殊的值。每向下走一层，就代表用了一次机会，使得当前的路花费为0，最多可以走k次。如例2.飞行路线。  
**3、** 有k个机会逆向行驶，我们可以建k张相同的该图，将每层图之间有边的两个点用的逆向的边连接。每向下走一层，就代表用了一次机会逆向走了一次，最多可以走k次。

#### 二、经典例题 ####

**例1：**[nc26257 小雨坐地铁 ][nc26257 _]  
![小雨坐地铁][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]

**思路：** 这就是建分层图的第一种情况，有k条地铁线路，我们就建k张图，然后再建第k+1张虚层，将各个可以中转线路的点连接起来，并设定从虚层到地铁需要乘该线的代价，从地铁到虚层代价为0，这里的虚层就相当于地铁站，这就实现了地铁的转线。

**代码解析：**

#include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int N = 510000,INF = 0x3f3f3f3f;	//注意数据范围
    typedef pair<int,int> PII;
    
    int e[N],ne[N],w[N],h[N],idx;	//链式前向星建图
    int n,m,s,t,dis[N];
    bool vis[N];
    priority_queue<PII,vector<PII>,greater<PII> > q;	//dijkstra优先队列优化
    
    void add(int a,int b,int c)	//加边函数
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	w[idx] = c;
    	h[a] = idx++;
    }
    
    int dijkstra(int s)	//dijkstra模板
    { 
    	memset(dis,INF,sizeof dis);
    	dis[s] = 0;
    	q.push({ 0,s});
    
    	while(!q.empty())
    	{ 
    		int u = q.top().second;
    		q.pop();
    		if(vis[u])
    			continue;
    		vis[u] = 1;
    		for(int i = h[u]; ~i;i = ne[i])
    		{ 
    			int v = e[i];
    			if(dis[v] > dis[u]+w[i])
    			{ 
    				dis[v] = dis[u]+w[i];
    				q.push({ dis[v],v});
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int price,ad,num,pre,cur;
    	cin >> n >> m >> s >> t;
    	memset(h,-1,sizeof h);
    	for(int i = 1;i <= m;i++)
    	{ 
    		cin >> price >> ad >> num;
    		for(int j = 0;j < num;j++)
    		{ 
    			cin >> cur;
    			if(j)
    			{ 
    				add((i-1)*n+pre,(i-1)*n+cur,ad);	//最重要的建图，k张图不需要单开k个数组建图，只需要每总点数n分成一层，类似于手动用一维数组模拟二维数组
    				add((i-1)*n+cur,(i-1)*n+pre,ad);	//同一线路的每站之间建一个无向边
    			}
    			add((i-1)*n+cur,n*m+cur,0);	//n*m层是虚层，点进虚层的花费是0
    			add(n*m+cur,(i-1)*n+cur,price);	//虚层进地铁的花费是该线路的费用
    			pre = cur;	//存储当前点，方便和下一个点建边
    		}
    	}
    
    	dijkstra(n*m+s);	//从虚层的起点开始跑
    	if(dis[n*m+t] == INF)	//答案是虚层的终点
    		cout << -1 << endl;
    	else
    		cout << dis[n*m+t] << endl;
    
    	return 0;
    }

--------------------

**例2：**[P4568 飞行路线][P4568]  
![飞行线路][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 1]  
**思路：** 分层图套路，最重要的就是建图，建k张相同的该图，各层内部正常连边，各层之间建边时，建一条从上到下花费为0的边，代表免费乘坐一次。跑一遍从s到n\*k+t的最短路即可。用一张洛谷大佬的图：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 2]

**代码解析：**

#include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int N = 2100010,INF = 0x3f3f3f3f;	//注意数据范围，经测验此题最多的边数达到了2100009
    typedef pair<int,int> PII;
    
    int n,m,k,s,t,dis[N];
    int e[N],ne[N],w[N],h[N],idx;	//链式前向星存图
    bool vis[N];
    priority_queue<PII,vector<PII>,greater<PII> > q;	//dijkstra优先队列优化
    
    void add(int a,int b,int c)	//加边函数
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	w[idx] = c;
    	h[a] = idx++;
    }
    
    void dijkstra(int s)	//dijkstra模板
    { 
    	memset(dis,INF,sizeof dis);
    	dis[s] = 0;
    	q.push({ 0,s});
    	while(!q.empty())
    	{ 
    		int u = q.top().second;
    		q.pop();
    		if(vis[u])
    			continue;
    		vis[u] = 1;
    		for(int i = h[u]; ~i;i = ne[i])
    		{ 
    			int v = e[i];
    			if(dis[v] > dis[u]+w[i])
    			{ 
    				dis[v] = dis[u]+w[i];
    				q.push({ dis[v],v});
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m >> k >> s >> t;
    	memset(h,-1,sizeof h);
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		add(a,b,c);	//关键的建图，各层内部正常建边
    		add(b,a,c);
    		for(int j = 1;j <= k;j++)	//从0到k层建k+1张图
    		{ 
    			add(j*n+a,j*n+b,c);	//每层内部正常建图
    			add(j*n+b,j*n+a,c);
    			add((j-1)*n+a,j*n+b,0);	//各层之间从上到下建边花费为0
    			add((j-1)*n+b,j*n+a,0);
    		}
    	}
    	for(int i = 0;i < k;i++)
    		add(i*n+t,(i+1)*n+t,0);	//为防止使用小于k次权力就到达终点，在每层的终点间建花费为0的边连起来
    
    	dijkstra(s);	//从起点s出发
    	cout << dis[n*k+t] << endl;	//到k层的终点为答案
    
    	return 0;
    }

[nc26257 _]: https://ac.nowcoder.com/acm/problem/26257
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0e1bbfd2fcc9483ea42006fa77038371.png
[P4568]: https://www.luogu.com.cn/problem/P4568
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/42b68976c45149d7800a7b208389a16f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/8e21c9bd8cdc42bc966624c919da0e4a.png