最短路 | 图论

参考《算法竞赛进阶指南》、AcWing题库

最短路

对于一张有向图 $^{\mathbb{}}$, 我们一般有邻接矩阵和邻接表两种存储方式。对于无向图, 可以把无向边看作两条方向相反的有向边, 从而采用与有向图一样的存储方式。因此, 在讨论最短路问题时, 我们都以有向图为例。

设有向图 $G=(V, E), V$ 是点集, $E$ 是边集, $(x, y)$ 表示一条从 $x$ 到 $y$ 的有向边, 其边权 (或称长度) 为 $w(x, y)$ 。设 $n=|V|, m=|E|$, 邻接矩阵 $A$ 是一个 $n * n$ 的矩阵, 我们把它定义为:

$$A[i, j]= \begin{cases}0 & i=j \\ w(i, j) & (i, j) \in E \\ +\infty & (i, j) \notin E\end{cases}$$

邻接矩阵的空间复杂度为 $O\left(n^{2}\right)$ 。

我们在链表与邻接表中已经讲解过了 “邻接表”, 并用数组模拟链表的形式进行了代码实现。长度为 $n$ 的表头数组 head 记录了从每个节点出发的第一条边在 ver 和 edge 数组中的存储位置, 长度为 $m$ 的边集数组 ver 和 edge 记录了每条边的终点和边权, 长度为 $m$ 的数组 next 模拟了链表指针, 表示从相同节点出发的下一条边在 ver 和 edge 数组中的存储位置。邻接表的空间复杂度为 $O(n+m)$ 。

// 邻接表：加入有向边(x, y)，权值为z
void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z; // 真实数据
	next[tot] = head[x], head[x] = tot; // 在表头x处插入
}

// 邻接表：访问从x出发的所有边
for (int i = head[x]; i; i = next[i]) {
	int y = ver[i], z = edge[i];
	// 一条有向边(x, y)，权值为z
}

单源最短路

单源最短路径问题 (Single Source Shortest Path, SSSP 问题) 是说, 给定一张有向图 $G=(V, E), V$ 是点集, $E$ 是边集, $|V|=n,|E|=m$, 节点以 $[1, n]$ 之间的连续整数编号, $(x, y, z)$ 描述一条从 $x$ 出发, 到达 $y$, 长度为 $z$ 的有向边。设 1 号点为起点, 求长度为 $n$ 的数组 $d i s t$, 其中 $d i s t[i]$ 表示从起点 1 到节点 $i$ 的最短路径的长度。

Dijkstra 算法（非负权图）

1. 初始化 $\operatorname{dist}[1]=0$, 其余节点的 dist 值为正无穷大。
2. 找出一个未被标记的、 $\operatorname{dist}[x]$ 最小的节点 $x$, 然后标记节点 $x$ 。
3. 扫描节点 $x$ 的所有出边 $(x, y, z)$, 若 $\operatorname{dist}[y]>\operatorname{dist}[x]+z$, 则使用 $\operatorname{dist}[x]+$ $z$ 更新 $\operatorname{dist}[y]$ 。
4. 重复上述 2～3 两个步骤, 直到所有节点都被标记。

Dijkstra 算法基于贪心思想, 它只适用于所有边的长度都是非负数的图。当边长 $z$ 都是非负数时, 全局最小值不可能再被其他节点更新, 故在第 1 步中选出的节点 $x$ 必然满足: $\operatorname{dist}[x]$ 已经是起点到 $x$ 的最短路径。我们不断选择全局最小值进行标记和扩展, 最终可得到起点 1 到每个节点的最短路径的长度。

时间复杂度

有多种方法来维护 2 操作中最短路长度最小的结点，不同的实现导致了 Dijkstra 算法时间复杂度上的差异。

• 暴力：不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在 $T$ 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 $O(m)$，1 操作总时间复杂度为 $O(n^2)$，全过程的时间复杂度为 $O(n^2 + m) = O(n^2)$。
• 二叉堆：每成功松弛一条边 $(u,v)$，就将 $v$ 插入二叉堆中（如果 $v$ 已经在二叉堆中，直接修改相应元素的权值即可），1 操作直接取堆顶结点即可。共计 $O(m)$ 次二叉堆上的插入（修改）操作，$O(n)$ 次删除堆顶操作，而插入（修改）和删除的时间复杂度均为 $O(\log n)$，时间复杂度为 $O((n+m) \log n) = O(m \log n)$。
• 优先队列：和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 $O(m)$ 的，时间复杂度为 $O(m \log m)$。
• Fibonacci 堆：和前面二者类似，但 Fibonacci 堆插入的时间复杂度为 $O(1)$，故时间复杂度为 $O(n \log n + m) = O(n \log n)$，时间复杂度最优。但因为 Fibonacci 堆较二叉堆不易实现，效率优势也不够大，算法竞赛中较少使用。
• 线段树：和二叉堆原理类似，不过将每次成功松弛后插入二叉堆的操作改为在线段树上执行单点修改，而 1 操作则是线段树上的全局查询最小值。时间复杂度为 $O(m \log n)$。

在稀疏图中，$m = O(n)$，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，$m = O(n^2)$，这时候使用暴力做法较二叉堆实现更优。

朴素 Dijkstra $O(n^2)$

时间复杂度为 $O\left(n^{2}\right)$, 主要瓶颈在于第 1 步的寻找全局最小值的过程。

存图方式：邻接矩阵

// Dijkstra算法，O(n^2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[3010][3010], d[3010];
bool v[3010];
int n, m;

void dijkstra() {
	memset(d, 0x3f, sizeof(d)); // dist数组
	memset(v, 0, sizeof(v)); // 节点标记
	d[1] = 0;
	for (int i = 1; i < n; i++) { // 重复进行n-1次
		int x = 0;
		// 找到未标记节点中dist最小的
		for (int j = 1; j <= n; j++)
			if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
		v[x] = 1;
		// 用全局最小值点x更新其它节点
		for (int y = 1; y <= n; y++)
			d[y] = min(d[y], d[x] + a[x][y]);
	}
}

int main() {
	cin >> n >> m;
	// 构建邻接矩阵
	memset(a, 0x3f, sizeof(a));
	for (int i = 1; i <= n; i++) a[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x][y] = min(a[x][y], z);
	}
	// 求单源最短路径
	dijkstra();
	for (int i = 1; i <= n; i++)
		printf("%d\n", d[i]);
}

堆优化 Dijkstra $O(m\log(n))$

可以用二叉堆 (C++STL priority_queue) 对 dist 数组进行维护, 用 $O(\log n)$ 的时间获取最小值并从堆中删除, 用 $O(\log n)$ 的时间执行一条边的扩展和更新, 最终可在 $O(m \log n)$ 的时间内实现 Dijkstra 算法。

严格来说, 时间复杂度为 $O((m+n) \log n)$ 。为方便起见, 我们假设 $m$ 的规模不小于 $n$ 的规模, 因此简写为 $\mathrm{O}(m \log n)$, 下略。

存图方式：邻接表

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], Next[M], d[N];
bool v[N];
int n, m, tot;
// 大根堆（优先队列），pair的第二维为节点编号
// pair的第一维为dist的相反数（利用相反数变成小根堆，参见0x71节）
priority_queue<pair<int, int>> q;

void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void dijkstra() {
	memset(d, 0x3f, sizeof(d)); // dist数组
	memset(v, 0, sizeof(v)); // 节点标记
	d[1] = 0;
	q.push(make_pair(0, 1));
	while (q.size()) {
		// 取出堆顶
		int x = q.top().second; q.pop();
	
		// 第一次出队即为最短路，只有第一次出队时用来扩展
		//if (x == endpoint) return; 如果只要求到终点的最短距离，直接结束
		if (v[x]) continue; //已经出队过，则已经用来扩展过，则跳过
		
		// 没有出队扩展过，现在是第一次，可以用来扩展，并标记
		v[x] = 1;
		
		// 扫描所有出边
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i], z = edge[i];
			if (d[y] > d[x] + z) {
				// 更新，把新的二元组插入堆
				d[y] = d[x] + z;
				q.push(make_pair(-d[y], y));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	// 构建邻接表
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	// 求单源最短路径
	dijkstra();
	for (int i = 1; i <= n; i++)
		printf("%d\n", d[i]);
}

Bellman-Ford 算法（可负环） $O(nm)$

给定一张有向图, 若对于图中的某一条边 $(x, y, z)$, 有 $\operatorname{dist}[y] \leq \operatorname{dist}[x]+z$ 成立, 则称该边满足三角形不等式。若所有边都满足三角形不等式, 则 dist 数组就是所求最短路。

我们先介绍基于迭代思想的 Bellman-Ford 算法。它的流程如下:

1. 扫描所有边 $(x, y, z)$, 若 $\operatorname{dist}[y]>\operatorname{dist}[x]+z$, 则用 $\operatorname{dist}[x]+z$ 更新 $\operatorname{dist}[y]$ 。
2. 重复上述步骤, 直到没有更新操作发生。

Bellman-Ford 算法的时间复杂度为 $O(n m)$ 。

这么做的含义是显然的：我们尝试用 $S \to u \to v$（其中 $S \to u$ 的路径取最短路）这条路径去更新 $v$ 点最短路的长度，如果这条路径更优，就进行更新。

Bellman-Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。

每次循环是 $O(m)$ 的，那么最多会循环多少次呢？

在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 $+1$，而最短路的边数最多为 $n-1$，因此整个算法最多执行 $n-1$ 轮松弛操作。故总时间复杂度为 $O(nm)$。

但还有一种情况，如果从 $S$ 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 $n-1$ 轮，因此如果第 $n$ 轮循环时仍然存在能松弛的边，说明从 $S$ 点出发，能够抵达一个负环。

title: 负环判断中存在的常见误区

需要注意的是，以 $S$ 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 $S$ 点出发不能抵达一个负环，而不能说明图上不存在负环。
    
因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman-Ford 算法。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], backup[N];

void add(int a, int b, int c) { // 添加一条边a->b，边权为c
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

/**
dist[1]=0,dist[其他点]=+∞  
for k 次 (迭代k次涵义：从s点经过不超过k条边的最短距离)  
	for 所有边 a->b w  
		dist[b]=min(dist[b],dist[a]+w) 松弛操作
**/
int bellmanford(int s, int k) {
  memset(dist, 0x3f, sizeof dist);
  dist[s] = 0;
  
  bool NegCyc;
  for (int i = 1; i <= k; ++i) { //经过不超过 k 条边
    NegCyc = false;
	  
	// 在进行新一轮循环前，一定要备份当前 dist 距离
	// 避免利用到，在当前循环中被扩展更新后的点数据，进行扩展
    memcpy(backup, dist, sizeof dist);//备份！！！
	  
    for (int u = 1; u <= n; ++u) {
      for (int j = h[u]; ~j; j = ne[j]) {
        int v = e[j], we = w[j];
        if (dist[v] > backup[u] + we) {
          dist[v] = backup[u] + we;
          NegCyc = true;
        }
      }
    }
    if (NegCyc == false) break; // 没有可以松弛的边时就停止算法
  }
  //如果一共有 k 个点，第 k 轮循环仍然可以松弛时，说明 s 点可以抵达一个负环
  if (NegCyc) cout << "存在负环" << endl;
	
  //因为有负边，dist[n] 可能比 0x3f3f3f3f 小
  if (dist[n] > 0x3f3f3f3f / 2) cout << "不能到达点 n ";
  
  return dist[n];	
}

int main() {
  memset(h, -1, sizeof h);
  
  cin >> n >> m >> k;

  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
  
  bellmanford(1, k);
  	
  if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible";
  else cout << dist[n];
}

SPFA 算法（可负环） $O(km) → O(nm)$

很多时候我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列（普通队列）来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。

SPFA 也可以用于判断 $s$ 点是否能抵达一个负环，只需记录最短路经过了多少条边，当经过了至少 $n$ 条边时，说明 $s$ 点可以抵达一个负环。

实际上, SPFA 算法在国际上通称为 “队列优化的 Bellman-Ford 算法”, 仅在中国大陆流行 “SPFA 算法” 的称谓。请读者回顾广搜变形一文中对 “广搜变形” 的讨论与总结。 SPFA 算法的流程如下:

1. 建立一个队列（普通队列）, 最初队列中只含有起点 1 。
2. 取出队头节点 $x$, 扫描它的所有出边 $(x, y, z)$, 若 $\operatorname{dist}[y]>\operatorname{dist}[x]+z$, 则使用 $\operatorname{dist}[x]+z$ 更新 $\operatorname{dist}[y]$ 。同时, 若 $y$ 不在队列中, 则把 $y$ 入队。
3. 重复上述步骤, 直到队列为空。

在任意时刻, 该算法的队列都保存了待扩展的节点。每次入队相当于完成一次 dist 数组的更新操作, 使其满足三角形不等式。一个节点可能会入队、出队多次。最终, 图中节点收敛到全部满足三角形不等式的状态。这个队列避免了 Bellman-Ford 算法中对不需要扩展的节点的冗余扫描, 在随机图上运行效率为 $O(k m)$ 级别, 其中 $k$ 是一个较小的常数。但在特殊构造的图上, 该算法很可能退化为 $O(n m)$, 必须谨慎使用。

SPFA不再能保证每个状态第一次入队时就能得到最小代价，所以只能允许一个状态被多次更新、多次进出队列。我们不断执行搜索，直到队列为空。

SPFA中的队列是普通队列，只记录需要待扩展的点，不需要将 dist 数据入队，直接修改更新 dist 值即可。Dijkstra中的队列是优先级队列，需要将 dist 数据一同入队，以便出队时找到最小距离的点。

SPFA：迭代思想 + 普通的BFS，每个点可能被更新（入队）多次，被用来扩展（出队）多次，只要出队，就会被用来扩展。

Dijkstra：优先队列 BFS，每个点可能被更新（入队）多次，但只被用来扩展一次，第一次出队时即为该点的最短距离，每个点仅在第一次出队时被用来扩展。

// SPFA算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], Next[M], d[N];
int n, m, tot;
queue<int> q;
bool v[N];

void add(int x, int y, int z) {
	ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void spfa() {
	memset(d, 0x3f, sizeof(d)); // dist数组
	memset(v, 0, sizeof(v)); // 是否在队列中
	d[1] = 0; v[1] = 1;
	q.push(1);
	while (q.size()) {
		// 取出队头
		int x = q.front(); q.pop();
		v[x] = 0;
		// 扫描所有出边
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i], z = edge[i];
			if (d[y] > d[x] + z) { // 更新，把新的二元组插入堆
				/**
				cnt[y] = cnt[x] + 1;  // 记录最短路经过的边数
				if (cnt[v] >= n) return false;
				// 在不经过负环的情况下，最短路至多经过 n - 1 条边
                // 因此如果经过了多于 n 条边，一定说明经过了负环
				**/
				d[y] = d[x] + z;
				if (!v[y]) q.push(y), v[y] = 1;
				//队列中已经有该点时，则只需要更新 dist 数据就行，
				//队列中不存在该点时，才需要将该点入队，表示该点待扩展
			}
		}
	}
}

int main() {
	cin >> n >> m;
	// 构建邻接表
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	// 求单源最短路径
	spfa();
	for (int i = 1; i <= n; i++)
		printf("%d\n", d[i]);
}

值得一提的是, 即使图中存在长度为负数的边, Bellman-Ford 和 SPFA 算法也能够正常工作。

另外, 如果图中不存在长度为负数的边, 那么类似于优先队列 BFS, 我们也可以使用二叉堆 (C++STL priority_queue) 对 SPFA 算法进行优化, 堆代替了一般的队列, 用于保存待扩展的节点, 每次取出 “当前距离最小” 的节点 (堆顶) 进行扩展, 节点第一次从堆中被取出时, 就得到了该点的最短路。这与堆优化 Dijkstra 算法的流程完全一致。“二叉堆优化基于贪心的 Dijkstra 算法” 和 “优先队列优化基于 BFS 的 SPFA 算法” 两种思想殊途同归, 都得到了非负权图上 $O(m \log n)$ 的单源最短路径算法。

---

340. 通信线路

在郊区有 $N$ 座通信基站，$P$ 条 双向 电缆，第 $i$ 条电缆连接基站 $A_i$ 和 $B_i$。

特别地，$1$ 号基站是通信公司的总站，$N$ 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 $i$ 条电缆需要花费 $L_i$。

电话公司正在举行优惠活动。

农产主可以指定一条从 $1$ 号基站到 $N$ 号基站的路径，并指定路径上不超过 $K$ 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 $1$ 行：三个整数 $N，P，K$。

第 $2..P+1$ 行：第 $i+1$ 行包含三个整数 $A_i,B_i,L_i$。

输出格式

包含一个整数表示最少花费。

若 $1$ 号基站与 $N$ 号基站之间不存在路径，则输出 $-1$。

数据范围

$0 \le K < N \le 1000$,
$1 \le P \le 10000$,
$1 \le L_i \le 1000000$

输入样例：

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6 

输出样例：

4 

算法分析

简单来说，本题是在无向图上求出一条从 $1$ 到 $N$ 的路径，使路径上第 $K+1$ 大的边权尽量小。

解法一：分层图最短路

可以仿照动态规划的思想, 用 $D[x, p]$ 表示从 1 号节点到达基站 $x$, 途中已经指定了 $p$ 条电缆免费时, 经过的路径上最贵的电缆的花费最小是多少 (也就是选择一条 从 1 到 $x$ 的路径, 使路径上第 $p+1$ 大的边权尽量小)。若有一条从 $x$ 到 $y$ 长度为 $z$ 的无向边, 则应该用 $\max (D[x, p], z)$ 更新 $D[y, p]$ 的最小值, 用 $D[x, p]$ 更新 $D[y, p+1]$ 的最小值。前者表示不在电缆 $(x, y, z)$ 上使用免费升级服务, 后者表示使用。

“动态规划” 一文的开头曾指出, 所谓 “无后效性” 其实告诉我们, 动态规划对状态空间的遍历构成一张有向无环图, 遍历顺序就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的 “状态”, 图中的边则对应状态之间的 “转移”, 转移的选取就是动态规划中的 “决策” 。显然, 我们刚才设计的状态转移是有后效性的。在有后效性时, 一种解决方案就是利用迭代思想, 借助 SPFA 算法进行动态规划, 直至所有状态收敛 (不能再更新)。

从最短路问题的角度去理解, 图中的节点也不仅限于 “整数编号”, 可以扩展到二维, 用二元组 $(x, p)$ 代表一个节点, 从 $(x, p)$ 到 $(y, p)$ 有长度为 $z$ 的边, 从 $(x, p)$ 到 $(y, p+1)$ 有长度为 0 的边。$D[x, p]$ 表示从起点 $(1,0)$ 到节点 $(x, p)$, 路径上最长的边最短是多少。这是 $N * K$ 个点, $P * K$ 条边的广义最短路问题, 被称为分层图最短路。对于非特殊构造的数据, SPFA 算法的时间复杂度为 $O(t N P)$, 其中 $t$ 为常数, 实际测试可以 AC 。本题也让我们进一步领会了动态规划与最短路问题的共通性。

// 解法一：分层图+堆优化Dijkstra
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1005, MAX_M = 20005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, k, d[MAX_N][MAX_N];
bool v[MAX_N][MAX_N];
// pair<-dist[x], pair<x, j>>
priority_queue<pair<int, pair<int, int>>> q;

// 插入一条从x到y长度z的有向边
void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x]; // 在head[x]这条链的开头插入新点
    head[x] = tot;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1][0] = 0;
    q.push(make_pair(0, make_pair(1, 0)));
    while (!q.empty()) {
        int i = q.top().second.first, j = q.top().second.second;
        q.pop();
        if (v[i][j]) continue;
        v[i][j] = true;
        for (int _ = head[i]; _; _ = nxt[_]) {
            int y = ver[_], z = edge[_];
            if (d[y][j] > max(d[i][j], z)) {
                d[y][j] = max(d[i][j], z);
                q.push(make_pair(-d[y][j], make_pair(y, j)));
            }
            if (j < k && d[y][j+1] > d[i][j]) {
                d[y][j+1] = d[i][j];
                q.push(make_pair(-d[y][j+1], make_pair(y, j+1)));
            }
        }
    }
    int ans = 0x7f7f7f7f;
    for (int j = 0; j <= k; j++) ans = min(ans, d[n][j]);
    if (ans == 0x7f7f7f7f) puts("-1");
    else cout << ans << endl;
}

解法二：二分答案，双端队列 BFS

本题的答案显然具有单调性, 因为支付的钱更多时, 合法的升级方案一定包含了花费更少的升级方案。所以我们可以二分答案, 把问题转化为: 是否存在一种合法的升级方法, 使花费不超过 mid。

转化后的判定问题非常容易。只需要把升级价格大于 mid 的电缆看作长度为 1 的 边, 把升级价格不超过 mid 的电缆看作长度为 0 的边, 然后求从 1 到 $N$ 的最短路是否不超过 $K$ 即可。在广搜变形一文中我们已经学习过, 可以用双端队列 BFS 求解这种边权只有 0 和 1 的最短路问题。整个算法时间复杂度为 $O\left((N+P) \log MAX\_L\right)$ 。

// 解法二：二分答案+双端队列BFS
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1005, MAX_M = 20005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, k, d[MAX_N];
deque<int> q;

// 插入一条从x到y长度z的有向边
void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x]; // 在head[x]这条链的开头插入新点
    head[x] = tot;
}

bool solve(int t) {
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;
    q.push_back(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i] > t ? 1 : 0;
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (z == 0) q.push_front(y); else q.push_back(y);
            }
        }
    }
    return d[n] <= k;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    int L = 0, R = 1000001;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (solve(mid)) R = mid; else L = mid + 1;
    }
    if (L == 1000001) puts("-1"); else cout << L << endl;
}

Solution

---

341. 最优贸易

$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。

任意两个城市之间最多只有一条道路直接相连。

这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。

$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。

但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 $C$ 国旅游。

当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。

设 $C$ 国 $n$ 个城市的标号从 $1 \sim n$，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。

在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 $n$ 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。

因为阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 $n$ 个城市的水晶球价格，$m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。

请你告诉阿龙，他最多能赚取多少旅费。

注意：本题数据有加强。

输入格式

第一行包含 $2$ 个正整数 $n$ 和 $m$，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。

接下来 $m$ 行，每行有 $3$ 个正整数，$x，y，z$，每两个整数之间用一个空格隔开。

如果 $z=1$，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。

输出格式

一个整数，表示答案。

数据范围

$1 \le n \le 100000$,
$1 \le m \le 500000$,
$1 \le 各城市水晶球价格 \le 100$

输入样例：

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2 

输出样例：

5 

算法分析

本题是让我们在一张节点带有权值的图上找出一条从 1 到 $n$ 的路径, 使路径上能选出两个点 $p, q$ (先经过 $p$ 后经过 $q$ ), 并且 “节点 $q$ 的权值减去节点 $p$ 的权值” 最大。

图中双向通行的道路可看作两条方向相反的单向通行道路。在下面的讨论中, 我们均把这张图视为有向图。除此之外, 我们再建立一张反图 (在原图基础上把所有边的方向取反后得到的图) 保存在另外一个邻接表中。

先以 1 为起点, 在原图上用 SPFA 或 Dijkstra 算法, 求出数组 $D$, 其中 $D[x]$ 表示从节点 1 到节点 $x$ 的所有路径中, 能够经过的权值最小的节点的权值。$D$ 数组的计算过程与单源最短路径的计算过程类似, 只需要把最短路中的 “用 $D[x]+w(x, y)$ 更新 $D[y]$ ” 改为 “用 $\min (D[x], price[y])$ 更新 $D[y]$ ” 即可, 其中 $price[y]$ 表示点 $y$ 的商品价格。

再以 $n$ 为起点, 在反图上用 SPFA 或 Dijkstra 算法, 求出数组 $F$, 其中 $F[x]$ 表示在原图上从节点 $x$ 到节点 $n$ (在反图上从 $n$ 到 $x$ ) 的所有路径中, 能够经过的权值最大的节点的权值。 $F$ 的计算方法与 $D$ 类似。

最后, 枚举每个节点 $x$, 用 $F[x]-D[x]$ 更新答案即可。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 100005, MAX_M = 1000005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, a[MAX_N], d[MAX_N]/*前缀min*/, f[MAX_N]/*后缀max*/;
bool v[MAX_N]; // 点是否在队列中
queue<int> q;

void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z; // 1表示只能正着走，-1表示只能倒着走，2表示正反都可以
    nxt[tot] = head[x];
    head[x] = tot;
}

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &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;
}

Solution

---

342. 道路与航线

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 $T$ 个城镇，编号为 $1 \sim T$。

这些城镇之间通过 $R$ 条道路 (编号为 $1$ 到 $R$) 和 $P$ 条航线 (编号为 $1$ 到 $P$) 连接。

每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ 到 $B_i$，花费为 $C_i$。

对于道路，$0 \le C_i \le 10,000$;然而航线的花费很神奇，花费 $C_i$ 可能是负数($-10,000 \le C_i \le 10,000$)。

道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$，花费都是 $C_i$。

然而航线与之不同，只可以从 $A_i$ 到 $B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 $S$ 把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数 $T,R,P,S$。

接下来 $R$ 行，每行包含三个整数（表示一个道路）$A_i,B_i,C_i$。

接下来 $P$ 行，每行包含三个整数（表示一条航线）$A_i,B_i,C_i$。

输出格式

第 $1..T$ 行：第 $i$ 行输出从 $S$ 到达城镇 $i$ 的最小花费，如果不存在，则输出 NO PATH。

数据范围

$1 \le T \le 25000$,
$1 \le R,P \le 50000$,
$1 \le A_i,B_i,S \le T$

输入样例：

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10 

输出样例：

NO PATH
NO PATH
5
0
-95
-100 

算法分析

本题是一道明显的单源最短路问题, 但图中带有负权边, 不能使用 Dijkstra 算法。 若直接用 SPFA 算法求解, 因为测试数据经过了特殊构造, 所以程序无法在规定时限内 输出答案。题目中有一个特殊条件一一双向边都是非负的, 只有单向边可能是负的, 并且单向边不构成环。我们应该利用这个性质来解答本题。

如果只把双向边（也就是题目中的 “道路” ) 添加到图里，那么会形成若干个连通块。若把每个连通块整体看作一个 “点”, 再把单向边 (也就是题目中的 “航线” ) 添加到图里, 会得到一张有向无环图。在有向无环图上, 无论边权正负, 都可以按照拓扑序进行扫描, 在线性时间内求出单源最短路。这启发我们用拓扑序的框架处理整个图, 但在双向边构成的每个连通块内部使用堆优化的 Dijkstra 算法快速计算该块内的最短路信息。

详细的算法流程如下:

1. 只把双向边加入到图中, 用深度优先遍历划分图中的连通块, 记 $c[x]$ 为节点 $x$ 所属的连通块的编号。
2. 统计每个连通块的总入度 (有多少条边从连通块之外指向连通块之内), 记 $\operatorname{deg}[i]$ 为第 $i$ 个连通块的总入度。
3. 建立一个队列 (存储连通块编号, 用于拓扑排序), 最初队列中包含所有总入度为零的连通块编号 (当然其中也包括 $c[S]$ 。 设 $d[S]=0$, 其余点的 $d$ 值为 $+\infty$ 。
4. 取出队头的连通块 $i$, 对该连通块执行堆优化的 Dijkstra 算法, 具体步骤为:
   • 4.1 建立一个堆, 把第 $i$ 个连通块的所有节点加入堆中。
   • 4.2 从堆中取出 $d[x]$ 最小的节点 $x$ 。
   • 4.3 若 $x$ 被扩展过, 回到步骤4.2, 否则进入下一步。
   • 4.4 扫描从 $x$ 出发的所有边 $(x, y, z)$, 用 $d[x]+z$ 更新 $d[y]$ 。
   • 4.5 若 $c[x]=c[y]$ (仍在连通块内) 并且 $d[y]$ 被更新, 则把 $y$ 插入堆。
   • 4.6 若 $c[x] \neq c[y]$, 则令 $\operatorname{deg}[c[y]]$ 减去 1 。若减到了 0 , 则把 $c[y]$ 插入拓扑排序的队列末尾。
   • 4.7 重复步骤4.2~4.6, 直至堆为空。
5. 重复步骤 4, 直至队列为空, 拓扑排序完成。

数组 $d$ 即为所求。整个算法的时间复杂度为 $0(T+P+R \log T)$ 。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 25005, MAX_M = 150005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], mark[MAX_M], nxt[MAX_M], tot;
int n, m, p, s, c[MAX_N], cnt, deg[MAX_N], d[MAX_N];
bool v[MAX_N];
queue<int> q; // 存的是块号
vector<int> a[MAX_N]; // 每个“道路”连通块中的点
priority_queue<pair<int, int>> heap;

void add(int x, int y, int z, int k) { // k==0双向, k==1单向
    ver[++tot] = y, edge[tot] = z, mark[tot] = k;
    nxt[tot] = head[x], head[x] = tot;
}

void dfs(int x) {
    c[x] = cnt;
    a[cnt].push_back(x);
    for (int i = head[x]; i; i = nxt[i]) {
        if (mark[i] == 1) continue;
        int y = ver[i];
        if (!c[y]) dfs(y);
    }
}

void dijkstra(int k) { // 算k这一块的最短路
    for (int j = 0; j < a[k].size(); j++) { // for (auto x : a[k]) {
        int x = a[k][j]; // x是点号，k这块里面的所有点
        heap.push(make_pair(-d[x], x));
    }
    while (!heap.empty()) {
        int x = heap.top().second;
        heap.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (mark[i] == 0) { // 正常的dijkstra模板
                if (d[y] > d[x] + edge[i]) {
                    d[y] = d[x] + edge[i];
                    heap.push(make_pair(-d[y], y));
                }
            } else {
                d[y] = min(d[y], d[x] + edge[i]);
                if (--deg[c[y]] == 0) q.push(c[y]); // 拓扑排序的更新
            }
        }
    }
}

int main() {
    cin >> n >> m >> p >> s;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, 0);
        add(y, x, z, 0);
    }
    for (int i = 1; i <= p; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, 1);
    }
    for (int i = 1; i <= n; i++)
        if (c[i] == 0) {
            cnt++;
            dfs(i);
        }
    // 统计每块的总入度，只看航线
    for (int x = 1; x <= n; x++)
        for (int i = head[x]; i; i = nxt[i]) {
            if (mark[i] == 0) continue;
            // 这是一条从块c[x]到块c[ver[i]]的航线
            deg[c[ver[i]]]++;
        }
    // 对块拓扑排序
    for (int i = 1; i <= cnt; i++)
        if (!deg[i]) q.push(i);
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    while (!q.empty()) {
        int k = q.front(); // k是块号
        q.pop();
        dijkstra(k);
    }
    for (int i = 1; i <= n; i++)
        if (d[i] > n * 10000) puts("NO PATH"); else printf("%d\n", d[i]);
}

Solution

---

任意两点间最短路径

为了求出图中任意两点间的最短路径, 当然可以把每个点作为起点, 求解 $N$ 次单源最短路径问题。不过, 在任意两点间最短路问题中, 图一般比较稠密。使用 Floyd 算法可以在 $O\left(N^{3}\right)$ 的时间内完成求解, 并且程序实现非常简单。

Floyd 算法

设 $D[k, i, j]$ 表示 “经过若干个编号不超过 $k$ 的节点” 从 $i$ 到 $j$ 的最短路长度。该问题可划分为两个子问题, 经过编号不超过 $k-1$ 的节点从 $i$ 到 $j$, 或者从 $i$ 先到 $k$ 再到 $j$ 。于是:

$$D[k, i, j]=\min (D[k-1, i, j], D[k-1, i, k]+D[k-1, k, j])$$

初值为 $D[0, i, j]=A[i, j]$, 其中 $A$ 为本节开头定义的邻接矩阵。

可以看到, Floyd 算法的本质是动态规划。 $k$ 是阶段, 所以必须置于最外层循环中。

$i$ 和 $j$ 是附加状态, 所以应该置于内层循环。这也解释了为何很多初学者按照 $i, j, k$ 的顺序执行循环, 会得到错误的结果。

与背包问题的状态转移方程类似, $k$ 这一维可被省略。最初, 我们可以直接用 $D$ 保存邻接矩阵, 然后执行动态规划的过程。当最外层循环到 $k$ 时, 内层有状态转移:

$$D[i, j]=\min (D[i, j], D[i, k]+D[k, j])$$

最终 $D[i, j]$ 就保存了 $i$ 到 $j$ 的最短路长度。

// Floyd算法，(n^3)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int d[310][310];
int n, m;

int main() {
	cin >> n >> m;
	// 把d数组初始化为邻接矩阵
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++) d[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x][y] = min(d[x][y], z);
	}
	// floyd求任意两点间最短路径
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	// 输出
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) printf("%d ", d[i][j]);
		puts("");
	}
}

传递闭包

在交际网络中, 给定若干个元素和若干对二元关系, 且关系具有传递性。 “通过传递性推导出尽量多的元素之间的关系” 的问题被称为传递闭包。

传递性: 设 $\odot$ 是定义在集合 $S$ 上的二元关系, 若对于 $\forall a, b, c \in S$, 只要有 $a \odot b$ 且 $b \odot c$, 就必然有 $a \odot c$, 则称关系 $\odot$ 具有传递性。

建立邻接矩阵 $d$, 其中 $d[i, j]=1$ 表示 $i$ 与 $j$ 有关系, $d[i, j]=0$ 表示 $i$ 与 $j$ 没有关系。特别地, $d[i, i]$ 始终为 1 。使用 Floyd 算法可以解决传递闭包问题:

// Floyd传递闭包
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool d[310][310];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) d[i][i] = 1;
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		d[x][y] = d[y][x] = 1;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] |= d[i][k] & d[k][j];
}

---

343. 排序

给定 $n$ 个变量和 $m$ 个不等式。其中 $n$ 小于等于 $26$，变量分别用前 $n$ 的大写英文字母表示。

不等式之间具有传递性，即若 $A>B$ 且 $B>C$，则 $A>C$。

请从前往后遍历每对关系，每次遍历时判断：

• 如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
• 如果发生矛盾，则结束循环，输出有矛盾；
• 如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含一个不等式，不等式全部为小于关系。

当输入一行 0 0 时，表示输入终止。

输出格式

每组数据输出一个占一行的结果。

结果可能为下列三种之一：

1. 如果可以确定两两之间的关系，则输出 "Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次数，'yyy...y'是指升序排列的所有变量。
2. 如果有矛盾，则输出： "Inconsistency found after t relations."，其中't'指迭代次数。
3. 如果没有矛盾，且不能确定两两之间的关系，则输出 "Sorted sequence cannot be determined."。

数据范围

$2 \le n \le 26$，变量只可能为大写字母 $A \sim Z$。

输入样例1：

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0 

输出样例1：

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined. 

输入样例2：

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0 

输出样例2：

Inconsistency found after 6 relations. 

输入样例3：

5 5
A<B
B<C
C<D
D<E
E<A
0 0 

输出样例3：

Sorted sequence determined after 4 relations: ABCDE. 

算法分析

这是一道 “有向” 的传递闭包问题, 需要在刚才思路的基础上稍作修改。对于每个形如 $i<j$ 的不等式, 令 $d[i, j]=1$ 。对于形如 $i>j$ 的不等式, 看作 $j<i$ 进行处理。除了 $i<j$ 之外的情况, 均有 $d[i, j]=0$ 。

使用 Floyd 算法对 $d$ 进行传递闭包。传递闭包完成后, 若存在变量 $i, j$, 使得 $d[i, j]$ 和 $d[j, i]$ 均为 1 , 则说明题目中给出的 $m$ 个不等式矛盾。若存在变量 $i, j$, 使得 $d[i, j]$ 和 $d[j, i]$ 均为 0 , 则说明题目中给出的 $m$ 个不等式不能确定每一对变量之间的大小关系。

若对于每对变量 $i, j, d[i, j]$ 和 $d[j, i]$ 有且仅有一个为 1 , 则说明能确定每对变量之间的大小关系。此时, 可以再用二分法, 二分 $t$ 的值, 判断仅用前 $t$ 个不等式能否达到上述条件。

//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m, d[N][N], e[N][N];

int floyd() {
	memcpy(e, d, sizeof(e));
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				e[i][j] |= e[i][k] & e[k][j];
				if (e[i][j] == e[j][i] && e[i][j] && i != j) return -1;
			}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (e[i][j] == e[j][i] && !e[i][j] && i != j) return 0;
	return 1;
}

void Sorting_It_All_Out() {
	memset(d, 0, sizeof(d));
	bool flag = 1;
	for (int i = 1; i <= m; i++) {
		char s[6];
		scanf("%s", s);
		d[s[0]-'A'][s[2]-'A'] = 1;
		if (flag) {
			int now = floyd();
			if (now == -1) {
				printf("Inconsistency found after %d relations.\n", i);
				flag = 0;
			} else if (now == 1) {
				printf("Sorted sequence determined after %d relations: ", i);
				pair<int, char> ans[N];
				for (int j = 0; j < n; j++) {
					ans[j].first = 0;
					ans[j].second = 'A' + j;
				}
				for (int j = 0; j < n; j++)
					for (int k = 0; k < n; k++)
						if (e[j][k]) ++ans[j].first;
				sort(ans, ans + n);
				for (int j = n - 1; j >= 0; j--) printf("%c", ans[j].second);
				puts(".");
				flag = 0;
			}
		}
	}
	if (flag) puts("Sorted sequence cannot be determined.");
}

int main() {
	while (cin >> n >> m && n) Sorting_It_All_Out();
	return 0;
}

Solution

---

344. 观光之旅

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示无向图有 $N$ 个点，$M$ 条边。

接下来 $M$ 行，每行包含三个整数 $u，v，l$，表示点 $u$ 和点 $v$ 之间有一条边，边长为 $l$。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

数据范围

$1 \le N \le 100$,
$1 \le M \le 10000$,
$1 \le l < 500$

输入样例：

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20 

输出样例：

1 3 5 2 

算法分析

无向图的最小环问题

考虑 Floyd 算法的过程。当外层循环 $k$ 刚开始时, $d[i, j]$ 保存着 “经过编号不超过 $k-1$ 的节点” 从 $i$ 到 $j$ 的最短路长度。

于是, $\min _{1 \leq i<j<k}\{d[i, j]+a[j, k]+a[k, i]\}$ 就是满足以下两个条件的最小环长度:

1. 由编号不超过 $k$ 的节点构成。
2. 经过节点 $k$ 。

上式中的 $i, j$ 相当于枚举了环上与 $k$ 相邻的两个点。故以上结论显然成立。

$\forall k \in[1, n]$, 都对上式进行计算, 取最小值, 即可得到整张图的最小环。

在该算法中, 我们对每个 $k$ 只考虑了由编号不超过 $k$ 的节点构成的最小环, 没有考虑编号大于 $k$ 的节点。事实上, 由对称性可知, 这样做并不会影响结果。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int a[310][310], d[310][310], pos[310][310];
int n, m, ans = 0x3f3f3f3f;
vector<int> path; //具体方案
void get_path(int x, int y) {
	if (pos[x][y] == 0) return;
	get_path(x, pos[x][y]);
	path.push_back(pos[x][y]);
	get_path(pos[x][y], y);
}
int main() {
	cin >> n >> m;
	memset(a, 0x3f, sizeof(a));
	for (int i = 1; i <= n; i++) a[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[y][x] = a[x][y] = min(a[x][y], z);
	}
	memcpy(d, a, sizeof(a));
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i < k; i++)
			for (int j = i + 1; j < k; j++)
				if ((long long)d[i][j] + a[j][k] + a[k][i] < ans) {
					ans = d[i][j] + a[j][k] + a[k][i];
					path.clear();
					path.push_back(i);
					get_path(i, j);
					path.push_back(j);
					path.push_back(k);
				}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
					pos[i][j] = k;
				}
	}
	if (ans == 0x3f3f3f3f) {
		puts("No solution.");
		return 0;
	}
	for (int i = 0; i < path.size(); i++)
		printf("%d ", path[i]);
	puts("");
}

有向图的最小环问题

对于有向图的最小环问题, 可枚举起点 $s=1 \sim n$, 执行堆优化的 Dijkstra 算法求解单源最短路径。$s$ 一定是第一个被从堆中取出的节点, 我们扫描 $s$ 的所有出边, 当扩展、更新完成后, 令 $d[s]=+\infty$, 然后继续求解。当 $s$ 第二次被从堆中取出时, $d[s]$ 就是经过点 $s$ 的最小环长度。

Solution

---

345. 牛站

给定一张由 $T$ 条边构成的无向图，点的编号为 $1 \sim 1000$ 之间的整数。

求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。

注意: 数据保证一定有解。

输入格式

第 $1$ 行：包含四个整数 $N，T，S，E$。

第 $2..T+1$ 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

输出格式

输出一个整数，表示最短路的长度。

数据范围

$2 \le T \le 100$,
$2 \le N \le 10^6$

输入样例：

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9 

输出样例：

10 

算法分析

虽然点的编号在 1~1000 之间, 但边最多只有 100 条。我们可以先对点的编号进行离散化, 把点的编号映射为 $1 \sim P$ 的整数, 其中 $P \leq 2 T$ 。

在离散化后, 设 $P * P$ 的邻接矩阵 $A$ 存储了图中的边。考虑以下方程:

$$\forall i, j \in[1, P], \quad B[i, j]=\min _{1 \leq k \leq P}\{A[i, k]+A[k, j]\}$$

我们可以认为 $A[i, j]$ 表示从 $i$ 到 $j$ 经过一条边的最短路。在上面的方程中, 对于每对二元组 $(i, j)$, 我们枚举了中转点 $k$, 从 $i$ 先到 $k$, 然后再到 $j$ 。因此 $B[i, j]$ 表示从 $i$ 到 $j$ 经过两条边的最短路。

一般地, 若矩阵 $A^{m}$ 保存任意两点之间恰好经过 $m$ 条边的最短路, 则:

$$\forall i, j \in[1, P], \quad\left(A^{r+m}\right)[i, j]=\min _{1 \leq k \leq P}\left\{\left(A^{r}\right)[i, k]+\left(A^{m}\right)[k, j]\right\}$$

回顾 “矩阵乘法”, 我们发现, 上式其实等价于一个关于 min 与加法运算的广义 “矩阵乘法” 。显然, 这个广义的 “矩阵乘法” 也满足结合律。因此, 我们可以用快速幕计算出 $A^{N}$, 具体的实现方法就是: 在计算一般的矩阵的幂的基础上, 把原来的乘法用加法代替, 把原来的加法用 $\min$ 运算代替。

最后, $\left(A^{N}\right)[S, E]$ 即为本题的答案。整个算法的时间复杂度为 $0\left(T^{3} \log N\right)$ 。

Solution

---