黑科技。

前言

分层图就是一种上层可以到达下层，而下层不可以到达上层的图。
其实重要的是一种构图方法。

如图，黑色的边就是一层图，蓝色的边就是上层连向下层的图。

EG1

P2939 [USACO09FEB]改造路Revamping Trails

题目描述

Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John's farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail's traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.

TIME LIMIT: 2 seconds

题意翻译

约翰一共有N)个牧场.由M条布满尘埃的小径连接.小径可 以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.

通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径，使之成为高 速公路.在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为0.

请帮助约翰决定对哪些小径进行升级，使他每天从1号牧场到第N号牧场所花的时间最短

Solve

枚举每个边设零，然后跑最短路？k=1可能还可以，但是k<=20，直接毙命。
分层图于是闪亮登场。其实这道题还可以用动态规划做，但是在这里我们只讨论分层图（其实是蒟蒻不会啦）
升级k条路径，就分k+1层图。第一层就是原图，每一层图内的点和边权都跟原图一样。但是层与层之间的边的边权为零。上层的u点连向下层的v点，边权为零，就相当于升级了这条小径，经过k层跑最短路到达n点，就相当于经过了已经升级了k条边的最短路。
不一定要升级k条边，所以取每层图的最小代价。

建图

for(int i=1;i<=m;i++){
	scanf("%d%d%d",&u,&v,&w);
	add(u,v,w);add(v,u,w);
	for(int j=1;j<=k;j++){
		add(u+j*n,v+j*n,w);
		add(v+j*n,u+j*n,w);
		add(u+(j-1)*n,v+j*n,0);
		add(v+(j-1)*n,u+j*n,0);//当然无向图需要双向
	}
}

tip:分层图重要的是构造图的方法,最短路的话，随便啦。但是还是说一句“SPFA死了”

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 10000000
using namespace std;
int n,m,k,ans;
int u,v,w;
int dis[N];
int head[N],len;
struct note{
	int to,vl,nxt;
}eg[N];
struct node{
	int u,vl;
	bool operator<(const node &a)const{
		return a.vl<vl;
	}
};
priority_queue<node> q;
bool vis[N];
void add(int u,int v,int w){
	len++;
	eg[len].to=v;
	eg[len].vl=w;
	eg[len].nxt=head[u];
	head[u]=len;
}
void dj(){
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push((node){1,0});
	while(!q.empty()){
		int e=q.top().u;
		q.pop();
		if(vis[e]) continue;
		vis[e]=true;
		for(int i=head[e];i;i=eg[i].nxt){
			int v=eg[i].to;
			if(dis[v]>dis[e]+eg[i].vl){
				dis[v]=dis[e]+eg[i].vl;
				if(!vis[v]) q.push((node){v,dis[v]});
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
		for(int j=1;j<=k;j++){
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
		}
	}
	dj();
	ans=dis[n];
	for(int i=1;i<=k;i++) ans=min(ans,dis[n+i*n]);
	printf("%d",ans);
	return 0;
}

后言

这个方法真的很适合图中优化几次边权然后求最小代价的题。话说这个题的数组范围是我二分出来的，一个个试出来的20000000太大，5000000太小。GG。

画外音

数据过大的话，分层图可能就GG了。而这个时候就该用其他的方法惹。

相关题目

P4822 [BJWC2012]冻结
P4568 [JLOI2011]飞行路线

关于

[例图取自]（https://www.luogu.org/blog/xiaohou/fen-ceng-tu）
封面不是啦。