关于 图论建模 的一些技巧

分层图思想

分层图在 最短路 中经常用到。

直观上讲，就是将一个图复制 k 倍，互相是平行的，即互不影响，分层图 两两之间 会有 决策边 相连。

这就等价于要在一个图上进行 k 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，也就是决策边。

一般有两种方法：

• 建图直接建 k + 1 层；
• 数组多开一维记录决策信息；（与dp思想相关）

Part Ⅰ

P1948 [USACO08JAN] Telephone Lines S

题目说明可以进行 k 次免费决策，考虑直接建 k + 1 层图。

对于一条路径 (x, y, w) ，如果考虑决策免费，那就等价于向下一状态连一条 0 边权的单向边，即 (x, y + n, 0)

建图完就可以直接 dij 跑图，

同时注意到所求答案要求是 一条满足条件的路径上的最大边权的最小值

也就是，对于当前访问到的点 y，(x, y, w) ，如果 1 ~ y 上原先记录的最小最大边权比前驱点 x 所记录的以及当前 w 比较都大了，

即 \(dist_y > \max(dist[x],~w)\) ，说明可以更新 \(dist_y = \max(dist[x],~w)\)，

这样就做到了 最小化最大边权的收敛。

注意：可能存在 k 次免费决策不必全部用完就可到达终点的情况，所以 k 次决策可能不全使用，因此对每个点要考虑当前状态不使用决策直接转移到下一状态，即连 (i, i + n, 0)

边数计算一下是要 \(2(k + 1)M + 2Mk + kN = 4MN + N^2\)，大概 5e7 的样子，不会超空间。

所以，很重要的是 分层图建图要考虑建图思路会不会超空间

#include <bits/stdc++.h>
#define re register int 
#define max(x, y) (x > y ? x : y)
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 10, M = 5e7 + 10, inf = 0x3f3f3f3f;
struct edge
{
	int to, w, next;
}e[M];
int top, h[N], dist[N];
int n, m, k;
bool vis[N];
priority_queue< pii, vector<pii>, greater<pii> > q;

inline void add(int x, int y, int w)
{
	e[++ top] = (edge){y, w, h[x]};
	h[x] = top;
}

inline void build(int a, int b, int c)
{
	add(a, b, c); 
	add(b, a, c);
	for (re i = 1; i <= k; i ++)
	{
		add(i * n + a, i * n + b, c);
		add(i * n + b, i * n + a, c);
		
		add((i - 1) * n + a, i * n + b, 0);
		add((i - 1) * n + b, i * n + a, 0);
	}		
}

inline bool dijkstra()
{
	memset(vis, false, sizeof(vis));
	for (re i = 0; i <= (k + 1) * n; i ++) dist[i] = inf;
	
	dist[1] = 0;
	q.push(make_pair(0, 1));
	
	while (!q.empty())
	{
		int x = q.top().second; q.pop();
		if (vis[x]) continue;
		vis[x] = true;
		
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to, w = e[i].w;
			if (dist[y] > max(dist[x], w))
			{
				dist[y] = max(dist[x], w);
				q.push(make_pair(dist[y], y));
			}
		}
	}
	
	return (dist[(k + 1) * n] == inf ? false : true);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	while (m --)
	{
		int a, b, c; cin >> a >> b >> c;
		build(a, b, c);
	}
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= k; j ++)
			add((j - 1) * n + i, j * n + i, 0);
			
	if (dijkstra()) cout << dist[(k + 1) * n] << '\n';
	else cout << "-1\n";
	
	return 0;
}