最短路杂题选讲笔记

P1462 通往奥格瑞玛的道路

题意

给定一个边和点都带权的无向图。给定距离限制，要求找出一条从$1$到$n$的路径，使得边权之和不超过限制。在此基础上，要求最大点权最小，或报告无解。

解法

显然答案是点权之一（废话），最大值最小启示我们二分。所以我们可以将点权排序一下，二分出最大点权最小值。

设正在二分判断答案是否能为$x$，将点权大于$x$的点禁掉，跑一遍最短路判断满不满足距离限制即可。 注意特判起点和终点的点权不能大于$x$。

P2149 Elaxia的路线

题意

给定边带权无向图和两对起终点，要求为每对起终点各找到一条路径，使得这两条路径都是各自的最短路。在此基础上最大化两条路径的公共边边权之和。

解法

设第一对起终点是$s1$和$t1$，第二对起终点是$s2$和$t2$，$w(u,v)$为$(u,v)$的边权，$dis(u,v)$为$(u,v)$之间的最短路。

根据最短路的性质，一条边$(u,v)$有可能成为从$s1$到$t1$的最短路，当且仅当

$$dis(s1,u)+w(u,v)+dis(v,t1)=dis(s1,t1)$$

我们可以分别跑一遍从$s1$开始和从$t1$开始的最短路处理出所有可能成为最短路的边，我们称它们为关键边。 然后我们可以从$s2$到$t2$跑一遍最优路，此时优先选择最短路，如果有多个最短路，就选择与关键边重叠得更长的。

根据最短路的性质，如果两条最短路（无论起终点是否相同）的公共边集一定构成一条链或空集。否则我们设它在$u$到$v$之间断开，我们可以让一条路径中$u$到$v$的子路径调整到另一条路径上，答案一定不会更劣。因此，最优路与关键边的重叠部分一定是一条链，并且存在一个合法的$s1$到$t1$的最短路完全包含这个重叠部分。 显然，计算最优路的时候就能计算完答案了。

UVA658 这不是bug，而是特性 P2761 软件补丁问题

题意

一个程序上有$n$种 Bug。为了修复这些 Bug，程序员开发了一些补丁。

补丁需要按顺序使用，一个补丁可以被使用多次也可以不被使用。使用一个补丁是有条件的，具体而言，它要求某些 Bug 必须存在，某些必须不存在，剩下的无所谓。使用一个补丁需要一定的时间。使用一个补丁后，某些 Bug 被修复，某些 Bug 又被制造出来了（一边修 Bug 一边写 Bug)，剩下 Bug 的存在与否不会改变。

请确定一个补丁使用的顺序，修复所有 Bug。输出修复所有 Bug 最小花费的时间，或报告无解。

解法

发现$n$很小，所以考虑状态压缩的思想，一个程序存在 Bug 的种类可以用一个二进制数表示。

然后枚举每个状态，再枚举补丁，如果这个补丁可以被使用就连一条从原状态到新状态的有向边，边权为补丁花费的时间。

最后跑一次最短路即可。

P2046 海拔

题意

一个$n×n$个点的网格，每个网格边有边权。

你需要为每个格点确定一个点权（可以为实数），使得左上角点权为$0$，右上角点权为$1$。定义每条网格边的代价为$两端点点权之差的绝对值×边权$，总代价为所有网格边代价之和。

请输出最小的总代价。

解法

首先证明点权在$[0,1]$之间。

将所有小于$0$的点权更改到$0$后，这些点内部的贡献变为$0$，因为没有其它点比这些点更小，所以这些点对外的贡献一定减少。同理可将所有大于$1$的点权更改到$1$。

然后证明点权是$0$或$1$，并且所有点权为$0$的点四连通，所有点权为$1$的点也四连通。

我们将一个点集称为极大连通块，当且仅当点集四连通，点集内点权一致且没有相邻点的点权等于点集点权。显然每个点属于且仅属于一个极大连通块。如果这个网格图的点权不满足上面的限制，则至少有$3$个极大连通块，那么至少有一个极大连通块是所有极大连通块（除了包含左上角哪个，记为左上连通块）中点权最小的，我们称之为关键连通块。关键连通块也不可能包含右下角。记关键连通块的点权为$x$。

如果关键连通块与左上连通块不相邻，设自己周边点中点权最小为$h$，显然$x<h$。那么将关键连通块的点权改为$h$一定更优（对外贡献减少，内部贡献一直为$0$）。 如果关键连通块与左上连通块相邻，设自己周边点中在左上连通块的点有$cnt1$个，设自己周边点中不在左上连通块的点有$cnt2$个且点权最小为$h$。如果$cnt1>cnt2$，则将关键连通块的点权改为$0$一定更优，否则改为$h$一定不劣。

综上，我们证明了结论，开始进一步研究如何最小化总代价。

研究一下左上连通块和右下连通块的分界线的性质。我们发现，分界线总是从左下部分开始，经过若干个网格中间，到达右上部分。注意分界线是有向的，并且分界线可以从任何贴着左边界和下边界网格边进入，从任何贴着右边界和上边界的网格边离开。

再研究这意味着多大的总代价。这条分界线会穿越一些网格边，而这些网格边恰好就是产生贡献的网格边。我们发现，如图，对于一条被分界线经过的网格边，分界线前进方向（注意不一定是我们看图的方向）的左侧的点是$0$，右侧的点是$1$，据此我们可以计算出一条分界线对应的总代价。

那么怎么最小化总代价呢？我们可以将网格中间（就是每个小正方形）都分别看成一个点，相邻的点之间连两条有向边，边权即为如果分界线按方向通过这条网格边产生的贡献。然后将左下部分和右上部分分别看成源点和汇点，源点向贴着左下部分的点连边，贴着右上部分的点向汇点连边，跑一遍最短路即可。

这种最短路就是对偶图最短路。

---

最短路

即在一个图上找到某些点到某些点的最短距离。

设 $n$ 为点数，$m$ 为边数。

bfs

若每个边权值都是 $1$，就可以打，时间复杂度优秀（$\mathcal{O(n)}$），码量小，思想简单。只需要按 bfs 序从起点对图进行遍历，起点到某个点的最短距离就是起点到最先转移到那个点的点的最短距离 $+1$。

void bfs(int s)
{
	q.push(s);
	d[s] = 0;
	vis[s] = true;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 0;i < g[u].size();i++)
		{
			int v = g[u][i];
			if(!vis[v])
			{
				vis[v] = true;
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	return;
}

Dijkstra

Dij就是对于每个点，计算最短路，再进行松弛操作，用于正权边。

时间复杂度$\mathcal O(n^2+m)$

可用优先队列、堆进行优化。

时间复杂度$\mathcal O(mlogm+m)$

算法是模型，建图方式也很重要。建好了好跑，建不好只能跪了！——Lily

模板题

直接c过来的模板

void dij()
{
	memset(d,127,sizeof(d));
	d[1] = 0;
	q.push((point){1,0});
	while(!q.empty())
	{
		int u = q.top().id;
		q.pop();
		vis[u] = true;
		for(int i = 0;i < g[u].size();i++)
		{
			int v = g[u][i].v;
			int w = g[u][i].w;
			if(vis[v]) continue;
			if(d[u] + w < d[v])
			{
				d[v] = d[u] + w;
				q.push((point){v,d[v]});
			}
		}
	}
	return;
}

SPFA

关于SPFA——

它死了

bi~

若存在负权路，就要用到 SPFA。因为若存在负权环，那么 dijkstra 算法就有可能会无限缩小最短路径

所以需要判环。如果一个节点被更新了 $n$ 次，就是有负权环。

非模板题

坦白说，题库中对负权图求最短路的简单题几乎没有，所以聪明的你们会发现本次作业很多都可以用dijkstra来解决。但是在以后随着对图论更深的学习，负权图是经常出现的，也就是说spfa算法还是会经常用到。

因此，本专题的题目希望同学们尽可能以spfa算法实现，熟悉spfa。——Lily

时间复杂度 $\mathcal O(nm)$~$\mathcal O(m)$，可以用栈、堆、双端队列等进行优化。

void spfa()
{
	q.push(1);
	is[1] = false;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		is[u] = false;
		for(int i = 0;i < g[u].size();i++)
		{
			int v = g[u][i].v;
			int w = g[u][i].w;
			if(d[u] + w < d[v])
			{
				d[v] = d[u] + w;
				if(!is[v])
				{
					is[v] = true;
					q.push(v);
				}
			}
		}
	}
	return;
}

Floyd

实现主要用的是动规原理。

如果点$i$和点$k$之间的边权加上点$k$和点$j$之间的边权小于$i$与$j$之间的最短路，更新。

即h[i][j] = min(h[i][j],h[i][k] + h[k][j])。

时间复杂度$\mathcal O(n^3)$

代码模型是不是超级简单好写？ 在数据范围友好的情况下，这种写法简直不要太香！ 但是一定要想明白，理解为什么节点间的状态可以这么转移。——Lily

模板

for(int k = 1;k <= n;k++)
{
	for(int i = 1;i <= n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			h[i][j] = min(h[i][j],h[i][k] + h[k][j]);
		} 
	}
}

总结

1. dijkstra：快，无法判负权回路。
2. SPFA：虽然时间那啥但是可以判负权环。
3. Floyd：慢，可以判负权环。主要是好写啊！