分层图

一、前言

在 PanH 学长的图论入门里看到了分层图的内容，遂学了一下，写文以记之。

分层图算是图论中的一种技巧，在普通的图论题中加入一些特殊条件时常常可以用到。

二、用途

一些图论题目，如最短路等，当题目规定 图上的边权可以改变（大多是减少）时，普通的算法难以发挥作用，就需要用到 分层图 的技巧。

三、思路

我们考虑怎么来处理修改边权的操作。首先最先想到的显然是枚举修改每一条边，这样的时间复杂度显然是无法承受的，考虑如何优化。

普通的最短路是在二维的平面上进行的，而为了处理修改边权的操作，我们将其引入，新增一维，将题目模型转化为了立体的三维图像，类似于一个世界的平行宇宙这样的概念。

说得这么玄乎，那到底要怎么实现呢？假设我们可以进行 $k$ 次修改边权的操作，就可以复制原来的平面图 $k$ 次，一共形成 $k+1$ 个平面图，第 $i$ 层图就表示进行第 $i$ 次操作后的图。在这么一个立体图中就包含了所有的情况。对于相邻层的图来说，对于边权的修改就决定了它们之间的联系。

更具体的来说，假设我们有 $k$ 次操作，操作为将一条边的边权变为 $0$ ，求最短路。如图：

对于每一条边我们都其复制成 $k+1$ 条边，每一层本身边权都为 原来的值，而在 连向相邻层 的边权变为修改后的值（这里是 $0$ ），表示该次操作修改这条边的权值。因此，我们最后可以得到每一种情况下的最短路。

最后还有一个问题：这样复制 $k+1$ 层图，时间和空间复杂度不会爆炸吗？答案是不会。由于每一层事实上是复制的，每一层其实都是非常相似的，计算也是几乎相同的，并不需要反复计算，问题的规模并没有变大。

四、实现

读入每一条边，将其复制为 $k+1$ 层（ $0,1,2,\ldots,k$ ）；
每一层自身的边权就是原来的边权，与相邻的层 边权为 修改后 的边权；
接下来按照普通的图论题目做即可；
最后统计答案要考虑 每一层 的情况。

五、例题

P4568 [JLOI2011]飞行路线

题意

$n$ 个点， $m$ 条边，有 $k$ 次操作，每次操作可以将一条边权值变为 $0$ ，求从出发点 $s$ 到终点 $t$ 的最短路。
思路

就是分层图的板子题。在普通的最短路之上加入了若干次修改权值为 $0$ 的操作，只需要建 $k+1$ 层的多层图即可。
代码

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

//普通的堆优化Dijkstra求最短路 
const int N=2e7+7;
int n,m,k,s,t;
int dis[N];
bool vis[N];
struct edge
{
	int to,nxt,dis;
}e[N];
int cnt,he[N];
void add(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].dis=w;
	e[cnt].nxt=he[u];
	he[u]=cnt;
}

 
struct node
{
	int pos,dis;
	
	bool operator < (const node &x)const 
	{
		return dis>x.dis;
	}
};

priority_queue<node>pq;

void dij()
{
	dis[s]=0;
	pq.push((node){s,0});
	
	while(!pq.empty())
	{
		int u=pq.top().pos;
		pq.pop();
		
		if(vis[u])
			continue;
		vis[u]=true;
		
		for(int i=he[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(vis[v])
				continue;
			
			if(dis[v]>dis[u]+e[i].dis)
				dis[v]=dis[u]+e[i].dis,pq.push((node){v,dis[v]});
		}
	}
}

int main()
{
	memset(dis,127,sizeof(dis));
	
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
		
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		
		add(u,v,w);//建初始图 
		add(v,u,w);
		
		for(int j=1;j<=k;j++)//将初始图复制k次 
		{
			add(u+j*n,v+j*n,w);//每一层自己到自己边权为初始值 
			add(v+j*n,u+j*n,w);
			add(u+j*n-n,v+j*n,0);//与相邻的层边权为0 
			add(v+j*n-n,u+j*n,0);
		}
	}
	
	dij();
	
	int ans=dis[t];
	
	for(int i=1;i<=k;i++)
		ans=min(ans,dis[t+i*n]);//注意最后答案要在每一层中取最优 
	
	printf("%d",ans);
	return 0;
}

P3831 [SHOI2012]回家的路

很妙的一道分层图。因为在换乘前只能横走或竖走，因此想到横纵坐标分开考虑。把换乘车站当成点建图，先按横坐标排序，横坐标相同的点建边，然后建第二张图（具体点编号就是原点编号加上 $m$ ），以纵坐标排序，纵坐标相同的点建边，然后跑最短路即可。

其他例题：

P1073 [NOIP2009 提高组] 最优贸易（正解并不是分层图，需要一些转换）
P2939 [USACO09FEB]Revamping Trails G（模板题）
UVA11374 Airport Express（普通分层图，只是需要 记录路径）
P4822 [BJWC2012]冻结（简单题）

六、参考

平土匀值的博客
《“分层图思想”及其在信息学竞赛中的应用》

Creator's World

分层图

分层图