2024.3.9 笔记

P1948

题目大意为在无向图上求出从 \(1\) 到 \(N\) 的路径，使路径上第 \(k+1\) 大的边权尽量少。

第一种是 DP 用\(f[i][j]\) 表示从 \(1\) 到点 \(i\)，用了 \(j\) 条免费线的最小花费。

对于一条 \(u -> v\) 的边 \(e\) 有转移：

不用免费线 \(f_{v,k}=min(f_{v,k},max(f_{u,k},c[e]))\)

用免费线 \(f_{v,k+1}=min(f_{v,k+1},f_{u,k})\)

第二种方法是二分答案双端队列 bfs

将原问题转化，是否存在一种合法的升级方法，使话费不超过 mid

现在考虑将升级价格大于 mid 的电缆看做长度为 1 的边，把升级价格不超过 mid 的电缆看做长度为 0 的边，求从 1 到 N 的最短路是否不超过 K 即可。复杂度为 \(O((N+P)log\) \(MAX_L)\)

P4568

经典分层图板子题了，用边权为 0 的边把各层连接起来正常跑最短路就可以了。

P1073

题目大意为在一张节点带有权值的图上找出一条从 1 到 \(n\) 的路径，使路径上能选出两个点 \(p,q\) 并且“节点 \(q\) 的权值减去节点 \(p\) 的权值最大”

可以考虑建一个正图和一个反图，先正向跑 SPFA，求出 \(D\) ，\(D[x]\) 表示从 \(1\) 到 \(x\) 的所有路径中，能够经过的权值最小的节点的权值。同理的，在反图中求出 \(F\)，记录最大。即可求出答案。

代码：

int d[MAX_N]/*前缀min*/, f[MAX_N]/*后缀max*/;
bool v[MAX_N]; // 点是否在队列中

// 求d数组，从st出发，只有标记为z和2的边可以用
void spfa(int *g, int st, int z)
{
	g[st] = a[st];
	q.push(st);
	v[st] = true;
	while (!q.empty()) 
	{
		int x = q.front();
		q.pop();
		v[x] = 0;
		for (rint i = h[x]; i; i = ne[i])
			if (w[i] == z || w[i] == 2) 
			{
				int y = v[i];
				int val = z == 1 ? min(g[x], a[y]) : max(g[x], a[y]);
				if (z == 1 && g[y] > val || z == -1 && g[y] < val) 
				{
					g[y] = val;
					if (!v[y]) q.push(y), v[y] = 1;
				}
			}
	}
}

int main() 
{
	cin >> n >> m;
	for (rint i = 1; i <= n; i++) cin >> a[i];
	for (rint i = 1; i <= m; i++) 
	{
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add(y, x, z == 1 ? -1 : z);
	}
	memset(d, 0x3f, sizeof(d));
	spfa(d, 1, 1); // 从1出发求前缀min（d），只有1和2的边可以用
	memset(f, 0xcf, sizeof(f));
	spfa(f, n, -1); // 从n出发倒着求后缀max（d），只有-1和2的边可以用
	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, f[i] - d[i]);
	cout << ans << endl;
}

P3008

直接 SPFA + SLF 可以过

正解的话则考虑优化，刚开始先只把双向边加入到图中，用深度优先遍历划分图中的联通块。统计每个联通块的总入度。然后跑 Dijkstra 和 拓扑就可以了。