分层图详解
一.前言
如果你是为了copy而来，就点击下方对应连接拿代码(本人也曾有过这种经历，为了方便大家，特此设立)
「BJWC2012」冻结题解
二.什么是分层图
2.1分层图的定义
顾名思义，分层图就是分成很多层的图(废话文学)
这其实是一种建模思想，并不是算法
这种思想通过建立多层相似或相同的图，并在图与图之间进行连边，以此实现两张图(两种性质)之间的转移
2.2怎么用分层图
给定N个点，M条边，允许对K条边进行改变(对权值进行一些改变，如把花费/2，变为0之类的)，求最短路的问题
2.3怎么建分层图
一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以进行此步状态转移
构建步骤分为两步
1.现将图分为k+1份(k为可操作的次数)
2.对于图中的每一条边
2.4怎么存图
这就涉及到了两种建图方式
2.4.1方式一：物理建图(博主like)
这种建图方式主要是建一维的，在一个维度上分段保存
eg.一张图有N个点，那就要建k+1层图(除了本身还有k层，所以是k+1)
所以我们只用建一个n*k长度的数列就可以表示
注意:此方法虽然好用，但却很费空间，所以还是算一下空间再使用
其中，对于第i张图的起点就应是(i-1)*n,因为0-n这个区间也是拿来存图的
代码实现
add(u,v,w);
add(v,u,w);
//添边是顺便
for(int i=1;i<=k;i++){
add(u+(i-1)*n,v+j*n,0);
add(v+(i-1)*n,u+j*n,0);//建双向边，所以每条边来回建两次
add(u+j*n,v+j*n,w);
add(v+j*n,u+j*n,w);
}
2.4.2方式二：逻辑建图(博主dislike)
这种建图方法是借助了DP的思想
将vis数组和dis数组多加一维
dis[i][j] 表示到达i用了j次免费机会的最小花费
vis[i][j] 表示到达i用了j次免费机会的最小花费是否出现
需要参与求解的实际问题的数据结构多加一维来模拟n层的效果
代码实现
struct node{
int tier//层数
int d;//到达该点的最短路
int num；//当前节点
}a[k*n];
三.例题
「BJWC2012」冻结
一.思路
最短路+分层图模板，详见我对这道题的TJ
二.代码
①.物理建图(代码写起来更方便，较易理解)
#include
using namespace std;
const int inf=0x3f3f3f3f;
int head[55*55],cnt=0;
struct edge{
int v;
int nex;
int w;
}e[1010*55*4];
void add(int u,int v,int w){//加边
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nex=head[u];
head[u]=cnt++;
}
int n,m,k;
int dis[55*55];
bool vis[55*55];
void dij(int s) {
memset(vis,0,sizeof(vis));
memset(dis,inf,sizeof(dis));
dis[s]=0;
//小根堆优化
priority_queue
q.push(make_pair(0,s)) ;
while(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}else{
vis[u]=1;
for(int i=head[u];~i;i=e[i].nex){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w) {
dis[v]=dis[u]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
}
int main(){
//初始化
memset(head,-1,sizeof(head));
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
//第0层
add(u,v,w);
add(v,u,w);
//建立k层
for(int j=1;j<=k;j++){
add(u+j*n-n,v+j*n,w/2);
add(v+j*n-n,u+j*n,w/2);
add(u+j*n,v+j*n,w);
add(v+j*n,u+j*n,w);
}
}
dij(1);
//循环看不同操作次数的min值
int ans=inf;
for(int i=0;i<=k;i++){
ans=min(ans,dis[n+i*n]);
}
cout< return 0; } ②.逻辑建图(有点难，费肝) #include using namespace std; const int maxn=55; const int maxk=55; int n,m,k; int ans=0x7f3f3f3f; int a,b,c; int dis[maxn][maxk]; int vis[maxn][maxk]; int first[maxn]; int nex[2010],v[2010],w[2010]; struct node{ int val; int u; int tot; }; bool operator<(node a,node b){ return a.val>b.val; } priority_queue int cnt; void add(int U,int V,int val){ v[++cnt]=V; w[cnt]=val; nex[cnt]=first[U]; first[U]=cnt; } int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a>>b>>c; add(a,b,c); add(b,a,c); } memset(dis,0x3f,sizeof(dis)); dis[1][0]=0; q.push({0,1,0}); while(q.size()){ int u=q.top().u; int tot=q.top().tot; q.pop(); if(vis[u][tot]){ continue; } vis[u][tot]=1; for(int i=first[u];i;i=nex[i]){ if(dis[v[i]][tot]>dis[u][tot]+w[i]){ dis[v[i]][tot]=dis[u][tot]+w[i]; q.push({dis[v[i]][tot],v[i],tot}); } if(tot dis[v[i]][tot+1]=dis[u][tot]+w[i]/2; q.push({dis[v[i]][tot+1],v[i],tot+1}); } } } for(int i=0;i<=k;i++){ ans=min(ans,dis[n][i]); } cout< return 0; }