分层图 - 用于边或者点有特殊限制的问题
分层图是一种将点拆开,复制多层图,并利用特殊构造的边(例如权值为0的边)将各层相连的建图方法。
一般用于 边或者点有特殊限制的问题 (如重复经过次数,多种价值可选,删掉一些边等)。
建图时层之间的边要和被限制的因素保持一致
需要保证拆开后的总点数规模可以接受。
例题1 Luogu P4568 [JLOI2011] 飞行路线 :
题目描述
有n个点m条边构成一张带权无向连通图,现在可以从中选出k条边将之权值变为0,求给定两点间的最短路径。
分层图的解决思路:
将图进行分层,建k + 1层图,每层内正常建边,层与层之间用权值为0的边相连,然后应用最短路算法求解即可。
假设我们的初始图如下,k = 1:
我们只需要再多建k层图,然后用权值为0的有向边跨层连接原图中对应的边,就可以保证我们从初始源点(S)走到第k + 1层的汇点(T + n*k)的最短路径上包含了k条权值为0的边。下图中蓝色边权值为0.
当然还会出现一种特殊情况:最短路径上的总边数小于k,也就是说可能最短路径在中间某层的汇点就已经达到了0,再向下走反而会使总路径增大。为了避免这种情况,我们可以在每两个相邻层的汇点之间连接一条权值为0的边。
C++ Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 5e5+10,M = 5e6 + 10;
int h[N],e[M],w[M],ne[M],idx;
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a], h[a] = idx++;
}
int n,m,k;
int S,T;
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[S] = 0;
priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,S});
while(!heap.empty()){
auto u = heap.top();heap.pop();
int ver = u.second,dis = u.first;
if(st[ver])continue;
st[ver] = true;
for(int i = h[ver];i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dis + w[i]){
dist[j] = dis + w[i];
heap.push({dist[j],j});
}
}
}
return dist[T + n*k];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&S,&T);
memset(h,-1,sizeof h);
while(m -- ) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
for(int i = 1; i <= k; ++i){
add(a + (i - 1)*n,b + i*n,0);
add(b + (i - 1)*n,a + i*n,0);
add(a + i*n,b + i*n,c);
add(b + i*n,a + i*n,c);
}
}
for(int i = 1; i <= k; ++i)add(T+(i-1)*n,T+i*n,0);
int t = dijkstra();
printf("%d\n",t);
return 0;
}
看懂了,好强啊!
tql!
请问一下,是怎么确认N,M最大值的
N是点的个数,M是边的个数,一般来说k层图点开单层的k倍, 边开单层的2k - 1倍。
感谢