分层图最短路
Kendrick_Z · · 个人记录
先占坑
首先我们先了解一下什么是分层图
就是说 我们建的图一般是只有一层的
那么我们看一张图就可以知道分层图的概念
图片如下：
没错分层图就是这么简单
干讲这个其实没什么用 那么我们结合一道例题：
JLOI2011 飞行路线
题目描述
Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
输入输出格式
输入格式：
数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。
接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。
输出格式：
只有一行，包含一个整数，为最少花费。
其实这道题看起来也是一个普通的最短路问题
但是我们分析一下题目
我们有k个操作
是可以免费搭乘
那么我们第一种思路就是简单的暴力枚举
枚举哪一种不选
然后最后取一个最小值
这种算法十分暴力 只能得到局部分数
那我们来考虑正解
没从也就是这篇Blog的核心
分层图
我们建立一个分层图一共有k层
第i层表示选择i次免费航线
那么我们在执行最短路的时候我们可以进行一次抉择（类似于动态规划）
到当前这一阶段时我们是否要进行使用免费航行
然后最后选择一个到终点的最优解就可以了
建图过程就是先正常建图
然后在不同的层之间建立一条免费航线 代表选择免费航行
那么的话我们建图跑一个最短路
那么我们最短路要选则哪一种算法呢？？
SPFA！
对不起卡我的SPFA
那么我们只能用dij+堆优化
来过这道题了
所以贴一下代码
#include <bits/stdc++.h>
using namespace std;
const int N=1E7+10;
const int MAXX=2147483647;
struct Edge{
int next,to,w;
}e[N<<1];
int head[N<<1],dis[N<<1],n,m,cnt,st,bg,k;
bool vis[N];
inline void add(int a,int b,int w){
cnt++;
e[cnt].next=head[a];
e[cnt].w=w;
e[cnt].to=b;
head[a]=cnt;
}
inline void dij(int s){
memset(dis,0x3f3f,sizeof(dis));
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
q.push(make_pair(0,s));
dis[s]=0;
while(!q.empty()){
int now=q.top().second;
q.pop();
if(!vis[now]){
vis[now]=1;
for(int i=head[now];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[now]+e[i].w){
dis[v]=dis[now]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&st,&bg);
for(int i=1;i<=m;++i)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,c);
for(int j=1;j<=k;++j)
{
add(u+(j-1)*n,v+j*n,0);
add(v+(j-1)*n,u+j*n,0);
add(u+j*n,v+j*n,c);
add(v+j*n,u+j*n,c);
}
}
for(int i=1;i<=k;i++)
{
add(bg+(i-1)*n,bg+i*n,0);}
dij(st);
printf("%d",dis[bg+k*n]);
return 0;
}那我们接下来看下面一道题
BJWC2012 冻结
题目描述
“我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？” “我要将有关魔法和奇迹的一切，封印于卡片之中„„”
在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。
现在，不需要立下契约也可以使用魔法了！你还不来试一试？ 比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。 例如，我们熟知的Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。 当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。 这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、„„ 当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。
我们考虑最简单的旅行问题吧： 现在这个大陆上有 N 个城市，M 条双向的道路。城市编号为 1~N，我们在 1 号城市，需要到 N 号城市，怎样才能最快地到达呢？ 这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。 现在，我们一共有 K 张可以使时间变慢 50%的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是：
在一条道路上最多只能使用一张 SpellCard。 使用一张SpellCard 只在一条道路上起作用。 你不必使用完所有的 SpellCard。
给定以上的信息，你的任务是：求出在可以使用这不超过 K 张时间减速的 SpellCard 之情形下，从城市1 到城市N最少需要多长时间。
输入输出格式
输入格式：
第一行包含三个整数：N、M、K。
接下来 M 行，每行包含三个整数：Ai、Bi、Timei，表示存在一条 Ai与 Bi之间的双向道路，在不使用 SpellCard 之前提下，通过它需要 Timei的时间。
输出格式：
输出一个整数，表示从1 号城市到 N号城市的最小用时。
这题看起来是一个非常有意思的题
题面肥肠长而且是一个生动的故事
但是其实就是一个普通的分层图
跟上面一道题完全是一样的
只不过就是不同的层之间 权值除以二
就行了
然后我贴一波代码
大家对照着这个代码就能理解了
const int MAXX=2147483647;
using namespace std;
struct Edge{
int next,to,w;
}e[1000000];
int head[1000000];
int n,m,k,cnt;
int dis[1000001];
bool vis[1000001];
inline void add(int x,int y,int w){
cnt++;
e[cnt].next=head[x];
e[cnt].w=w;
e[cnt].to=y;
head[x]=cnt;
}
inline void spfa(){
queue<int>q;
for(int i=1;i<=n*(k+1);i++){
dis[i]=MAXX;
vis[i]=false;
}
dis[1]=0;
vis[1]=1;
q.push(1);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[x]+e[i].w){
dis[v]=dis[x]+e[i].w;
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
vis[x]=0;
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int u,v,t;
scanf("%d%d%d",&u,&v,&t);
for(int j=0;j<=k;j++){//分层图建图
add(u+j*n,v+j*n,t);
add(v+j*n,u+j*n,t);
}
for(int j=0;j<k;j++){
add(u+j*n,v+(j+1)*n,t>>1);
add(v+j*n,u+(j+1)*n,t>>1);
}
}
spfa();
int ans=MAXX;
for(int i=0;i<=k;i++){
ans=min(dis[n+i*n],ans);
}
printf("%d",ans);
return 0;
}
很良心呢！
这道题可以用SPFA卡过！！！
不是卡过
SPFA就是正解
所以分层图的讲解就结束了
写在后面：
分层图其实比较好理解
关键是和其他图论算法的结合
能否成功的建立模型 然后就可以进行最短路 网络流等算法
同时如果开一维数组dis
记得控制好空间！！！
不要MLE也不要RE!!!!