分层图

· · 个人记录

前言

使用邻接表存图，不习惯用的可以理解下思路

正文

什么是分层图？

这是一种问题的算法，基础模型为：

一张图（有向无向、有环无环均可）上，有k次机会可以使过一条边不需要花费（即花费0），求起点到终点最短路

比如板子题P2939 [USACO09FEB]Revamping Trails G

分层图怎么解决？

我们可以将一个点建k+1次（一次是原图，剩余k都用于免费路径）。原因：我们可以免费k次。但很多方式都不能保证最短路最短。目前也没有任何其它算法可以保证最短（比如两次失败的贪心分层图想法）

细细的讲，我们先建一个原图，将原图复制一份，再复制一份……复制k次，直至有k+1个图为止。然后我们在每个复制出来的图中，将原图中每个图的起点连到下一个图的终点（使第i层的起点u连接第i+1层的终点v）

这样的目的是：因为可以免费k次，同一次走法中，我们的免费路径有k条。但因为无法控制最后结果的最短性，我们将每条可以免费的路径都免费，到达这一层之后直接通过两层直接连接的免费路径到下一层（因为免费路径肯定能最优）

最后直接正常跑个最短路即可

实现

这里用板子题的代码来讲解（可以当是题解）

一开始我想用全部二维数组来解决，后来觉得太麻烦就用一维存储

主要讲讲存图建边和输出吧其实因为其它的都和正常最短路一模一样

存图（建边）

其实用vector或者二维edge更舒坦，但是我比较喜欢用一维edge(雾

首先，建边时我们读入的u,v,w（代表起点、终点、权值）直接建一次边（此题无向边）

add_edge(u,v,w);
add_edge(v,u,w);

然后分k次存，为了好辨别所以前面先单存一次边其实是因为没推出来式子

我们的任务是：每次循环中建立这一层的原图，以及与上一层连接的免费路径（这里i是1开始到k循环，所以要存前面的，往后面存就错了）

式子自己理解下吧，不多讲了

for(int j=1;j<=k;j++){
    add_edge(n*j+u,n*j+v,w);//大边
    add_edge(n*j+v,n*j+u,w);//反大边
    add_edge(n*(j-1)+u,n*j+v,0);//大边0
    add_edge(n*(j-1)+v,n*j+u,0);//反大边0
}

输出

一开始我是循环所有的边找出最小，后来发现不对，改成这样：

int ans=dis[n];
for(int i=1;i<=k;i++){
    ans=min(ans,dis[(i+1)*n]);
}cout<<ans<<endl;

意思就是从第1层的n一直到第k+1层的n找出最小值，初始随便默认个，这里选的第一层的n

后来一想，无疑选择k条免费路径总是最合算的，就将输出改成了

cout<<dis[n*k+n]<<endl;

发现同样原理

代码

注意！因为一口气存了很多层，所以edge数组一点要开大一点！

我这里的数组是随便开了一点

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXM=100*50000+9;
struct Edge{
    int nxt,to,w;
}edge[MAXM];
struct priority{
    int id,w;
    bool operator <(const priority &x)const{return w>x.w;}
};
int n,m,k;
priority_queue<priority>q;
int num_edge=0,head[MAXM],dis[MAXM];
bool path[MAXM];
void add_edge(int from,int to,int w){
    edge[++num_edge]=(Edge){head[from],to,w};
    head[from]=num_edge;
}void Dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(path,0,sizeof(path));
    q.push((priority){s,0});
    dis[s]=0;
    while(!q.empty()){
        priority x=q.top();
        q.pop();
        int id=x.id;
        if(path[id])continue;
        path[id]=1;
        for(int i=head[id];i;i=edge[i].nxt){
            int to=edge[i].to;
            if(dis[to]>dis[id]+edge[i].w){
                dis[to]=dis[id]+edge[i].w;
                q.push((priority){to,dis[to]});
            }
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
        for(int j=1;j<=k;j++){
            add_edge(n*j+u,n*j+v,w);//大边
            add_edge(n*j+v,n*j+u,w);//反大边
            add_edge(n*(j-1)+u,n*j+v,0);//大边0
            add_edge(n*(j-1)+v,n*j+u,0);//反大边0
        }
    }Dijkstra(1);
//  int ans=dis[n];
//  for(int i=1;i<=k;i++){
//      ans=min(ans,dis[(i+1)*n]);
//  }cout<<ans<<endl;
    cout<<dis[n*k+n]<<endl;
    return 0;
}