【分层图】
【分层图是什么】
分层图，顾名思义
就是分很多层的图
也就是类似二维数组
不再是一个单一的平面
而是一个立体化的东西
不只有长宽，也有了自己的厚度
即为层数
【分层图可以用来干什么呢】
有的题目中会说到
让你免费建立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);
}
}