AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP

昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

今天查看题解，发现有几个重要的，从未考虑过的trick：

1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

重新定义状态$f(i, x)$为“恰好经过$i$次转移，到达节点$x$的所有路径中最大边权最小值（瓶颈路）”。设存在一些边$e_j:= u_j \rightarrow v_j$，边权为$w_j$，则我们有$$f(i, v_j)=\min\{\max (f(i-1, u_j), w_j)\}$$

问题来了：一般的矩阵乘法递推只适用于只包含数乘$\times$和数加$+$的运算，为什么取$\min, \max$的运算也符合条件？

3. 若在集合$R$上有二元运算$\space \cdot \space, +$，满足以下条件：
   • $(R, +)$是带有单位元$\mathbf{0}$的交换幺半群：
     • 满足结合律：$(a+b)+c = a+(b+c)$；
     • 对于单位元有：$\mathbf{0}+a=a+\mathbf{0}=a$；
     • 满足交换律：$a+b=b+a$。
   • $(R, \cdot)$是带有单位元$\mathbf{1}$的幺半群：
     • 满足结合律：$a\cdot(b\cdot c)=(a\cdot b)\cdot c$；
     • 对于单位元有：$\mathbf{1} \cdot a = a \cdot \mathbf{1} = a$。
   • 运算$\cdot$对运算$+$有分配律：
     • $(a+b)\cdot c=a \cdot c + b \cdot c$。
   • $0$可以吸收$R$：
     • $\mathbf{0}\cdot a = a \cdot \mathbf{0} = \mathbf{0}$。

   则我们称集合$R$为一个半环。

对于全面的关于“群”的性质，请移步群论。

只要是一个半环，那么矩阵乘法对该集合的两种运算均成立。

考虑矩阵乘法的定义。两个矩阵$A, B$的积为：$${\displaystyle (AB)_{ij}=\sum _{r=1}^{n}a_{ir}b_{rj}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}}$$其中只包含有运算$+, \cdot$（$a \cdot b$可略作$ab$），则若所有元素$a, b$处于一个（半）环中，根据定义可知，矩阵乘法可以应用于该集合中的元素。

现在我们回到这道题上来。我们定义运算$(\max, \cdot)$以及$(\min, +)$，它们在外层取$\min$不调换顺序的情况下，满足交换律、结合律。可以发现，原DP转移方程可以写作$$\begin{align} f(i, v_j) &=\min\{\max (f(i-1, u_{j1}), w_{j1}), \max (f(i-1, u_{j2}), w_{j2}), \dots\} \newline &=\sum f(i-1, u_j)\cdot w_j \end{align}$$

这满足半环的定义，所以我们就可以使用矩阵乘法愉快地递推了。更具体地，我们定义状态矩阵$A$，有$$A_{i, j}= \begin{cases} w_k, & \exists k, e_k:= j \rightarrow i \newline \inf, &\text{otherwise} \end{cases}$$，然后由矩阵乘法的结合律可知，计算$A^l$后将其与原状态矩阵$F$相乘即可。

更一般的，我们发现以下集合中的运算均满足半环的性质：

1. 定义在实数集$\mathbb{R}$上的数乘$\times$和数加$+$；
2. 定义在集合$A := \mathbb{R}\cup \{-\infty \}$上的运算$(\max, +)$和普通数乘$(\times, \cdot)$；
3. 定义在集合$A := \mathbb{Z} \cup [1, 2^n)$的运算$(逻辑异或 \oplus, +)$和$(逻辑与, \cdot)$；
4. (upd 04.28) 定义在实数集$\mathbb{R}\cup \{+ \infty\}$上的运算$(\min, +)$和数加$(+, \cdot)$。

总而言之，发现递推次数极大，且发现其包含的运算满足结合律和交换律时，一般考虑矩阵乘法加速递推。

Submission #28768750

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

template <typename T> inline bool read (T &x) {
	x = 0; int f = 1; char c = getchar ();
	for (; c != EOF && !isdigit (c); c = getchar ())
		if (c == '-') f = -1;
	if (c == EOF) return 0;
	for (; c != EOF && isdigit (c); c = getchar ())
		x = (x<<1) + (x<<3) + (c^48);
	x *= f; return 1;
}
template <typename T, typename... Targs>
inline bool read (T &x, Targs&... args) {
	return read (x) && read (args...); }
template <typename T> void print (T x) {
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) print (x / 10);
	putchar ('0' + x % 10);
}
template <typename T, typename... Targs>
inline void print (T x, Targs... args) {
	print (x), putchar (' '), print (args...); }
#define reint register int
#define inl inline
#define newl putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
typedef pair <int, int> pint;

constexpr int N = 105, INF = 0x3f3f3f3f;
int n, t, l, w[N][N], x, y;

struct matrix {
	int **mat, h, w;
	matrix () {}
	matrix (int x, int y) {
		h = x, w = y;
		mat = new int*[h + 1];
		for (int i = 1; i <= h; ++i) {
			mat[i] = new int[w + 1];
			for (int j = 1; j <= w; ++j)
				mat[i][j] = INF;
		}
	}
	inl int * operator [] (int x) { return mat[x]; }
	friend matrix operator * (matrix &a, matrix &b) {
		matrix c (a.h, b.w);
		for (int i = 1; i <= a.h; ++i)
			for (int j = 1; j <= b.w; ++j)
				for (int k = 1; k <= a.w; ++k)
					c[i][j] = /* + 运算 */ min (c[i][j], /* · 运算 */max (a[i][k], b[k][j]));
		return c;
	}
	inl matrix & operator *= (matrix &b) {
		matrix c = (*this) * b;
		return (*this) = c;
	}
};
matrix trans, f;

inl matrix fpow (matrix a, int b) {
	matrix res; bool flag = 0;
	for (; b; b >>= 1) {
		if (b & 1) {
			if (flag) res *= a;
			else res = a, flag = 1;
		}
		a *= a;
	}
	return res;
}

int main () {
	/* ABC236G Good Vertices 吴秋实 */
	read (n, t, l);
	for (int i = 1; i <= t; ++i) 
		read (x, y), w[x][y] = i;

	trans = matrix (n, n);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (w[i][j]) trans[j][i] = w[i][j];

	trans = fpow (trans, l);
	f = matrix (n, 1); f[1][1] = 0;
	f = trans * f;
	for (int i = 1; i <= n; ++i)
		print (f[i][1] != INF ? f[i][1] : -1), putchar (' ');

	return 0;
}