https://www.cnblogs.com/acioi/p/11716483.html

https://www.cnblogs.com/lijilai-oi/p/11285708.html

https://wenku.baidu.com/view/b15e2fbea1c7aa00b52acb96.html 例题讲解（百度文库）

http://www.doc88.com/p-61770953932.html 集训队论文

模板洛谷P2939 [USACO09FEB]改造路Revamping Trails

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 4100005
int n,m,head[N],tot,to[N],nxt[N],w[N],k,ans=0,dis[N];
bool vis[N];
void add(int u,int v,int w1)
{
    nxt[++tot]=head[u];head[u]=tot;to[tot]=v;w[tot]=w1;
}
priority_queue < pair<int,int> >q;
void dij()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[1]=0;q.push(make_pair(0,1));
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(vis[u])continue;vis[u]=1;
        for(int e=head[u];e;e=nxt[e])
        {
            int v=to[e];
            if(dis[v]>dis[u]+w[e])
            {
                dis[v]=dis[u]+w[e];
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}
int main()
{
    int u,v,w1;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w1);
        add(u,v,w1);add(v,u,w1);
        for(int j=1;j<=k;j++)
        {
           add(n*j+u,n*j+v,w1);add(n*j+v,n*j+u,w1);
           add(n*(j-1)+u,n*j+v,0);add(n*(j-1)+v,n*j+u,0);
        }
    }
    dij();
    ans=0x3f3f3f3f;
    for(int i=1;i<=k+1;i++)
    ans=min(ans,dis[i*n]);
    cout<<ans<<endl;
    return 0;
}

View Code

【分层图】

【分层图】

【分层图是什么】

分层图，顾名思义
就是分很多层的图
也就是类似二维数组
不再是一个单一的平面
而是一个立体化的东西
不只有长宽，也有了自己的厚度
即为层数

【分层图可以用来干什么呢】

有的题目中会说到
让你免费建立k条边
这个时候就可以用到分层图了

不过建多层图时间空间消耗都巨大,
因此适用的数据范围一般较小

多层的图，不同的状态
这里面之间可以转移
这里的状态有点类似动态规划
表示层数和情况状态
假设免费建立k条边
所以就可以有k层图表示已经免费建立了1条边到免费建立了k条边
如果现在你是出于第i个点，你已经建立了j条免费的边
你的下一个点是acioi，不过到acioi需要花费很多
所以就要建立一条免费的边
这个时候就连接到第j+1层的acioi这点了
第j+1层acioi的点这个状态用来j+1条边
比转移之前多用了一条边
也就是i到acioi的这条边
这就是分层图了

【分层图的实现】

在连接每两个点的同时
将复制出来的另外k个图上对应的两个点连接起来
也将i图和j图上的对应的点连接起来
也就是让这条边权值为零的情况
核心代码

for(register int i = 1;i <= m;++ i)
{
    int x,y,z;
    cin >> x >> y >> z;
    add(x,y,z),add(y,x,z);
    for(register int j = 1;j <= k;++ j)
    {
        add(j * n + x,j * n + y,z);//将其他图对应的边连接起来
        add(j * n + y,j * n + x,z);
        add((j - 1) * n + x,j * n + y,0);//两张图的连接点
        add((j - 1) * n + y,j * n + x,0);
    }
}

【例题】

P2939 [USACO09FEB]改造路Revamping Trails
分层图模板题
题解戳这里

P4822 [BJWC2012]冻结
分层图模板提
题解戳这里

P4568 [JLOI2011]飞行路线
分层图模板提
题解戳这里

综上所述：
分层图开空间需要好好斟酌一下

————————————————————————————————————————————————————————————————

浅谈分层图最短路问题

分层图最短路问题，就是把一个图分层然后跑最短路（废话）。

分层图最短路问题关键在于怎么分层，分层通常是起到对题中某个条件的限定作用，这里我们结合例题看看。

Luogu P4568飞行路线

题意大致是给一个带权无向图，允许k次飞行费用为0，求最小费用。

这里就是将图分成k层，每次从第i-1层到第i层相当于是走了一条免费的飞行路线。然后如果从第i层回到第i-1层就是一个“后悔”的过程。因此建图方法就是每层之间正常连边，层与层之间上到下边权为0，下到上正常边权。这样直接跑Dijkstra就好了。这里分层就是对k次免费进行限制，而且连反向的边保证程序有反悔的机会。

搬运一个大佬题解里的图。

P4568

Luogu P1073最优贸易

题意要求我们从一个点买入，一个点卖出，获得的费用最大，并且从1能到达n。

emmmm这个题题解里有很多玄学做法，这里只讨论分层图做法。我们暴力的想一想，每一个点都有可能买入，每一个点都有可能卖出，但是必须先买入再卖出（显然的嘛）。所以这其实就存在一个依赖关系。这样就可以将图分成3层，第一层表示没有买入和卖出，第二层表示已经买入，第三层表示已经卖出。那么每层内部正常连边（边权为0），层与层之间，第一层到第二层要连边权为-a[u]（u为第一层内边的起点，a[u]为费用）表示买入，第二层到第三层连边权为a[u]的边表示卖出。而第二层第三层回不到第一层就是我们限制了贸易次数，只进行一次贸易。这样图就建好了。

仍然搬运大佬题解的图。

P1073

总结一下，分层图最短路通常是按照题中的限制关系进行分层，通过层与层间的连通与否，边权进行限制，从而实现在跑最短路时也能兼顾限制条件。同时由于最短路算法是枚举点进行松弛，无法保证一次就得到最优解，因此往往通过一些方法实现“反悔”操作，例题1就是通过回到原来的层实现的，而例题2则是通过spfa不断松弛实现的。