最短路问题（四）

Bellman-Ford 负环

执行 $\text{bellman-ford}$ 算法的时候，如果迭代了 $n-1$ 次还可以进行边的松弛操作
那么一定存在负圈，实际上，如果用队列优化，迭代了 $n-1$ 次，也就是说对某个节点 $u$，入队了 $n$ 次

在编程实现上，需要 $\text{inq}(u)$ 判断点 $u$ 是否在队列中
同时需要 $\text{cnt}(u)$ 记录 $u$ 入队次数
初始化时，将距离向量 $\forall u, f(u) \leftarrow +\infty, \quad f(s) = 0$
由于一开始要将所有点进行松弛，所以 $\forall u \in [1, n], \ \text{Q}.\text{push}(u), \ \text{inq}(u) = 1$

Going in Cycle
对于 $G(n, m)$ 的有向图，求平均值最小的回路

不难想到用二分求解，边的平均权值的值域为 $[l, r]$，本例为浮点数二分
$\text{check}(mid)$ 表示是否存在平均权值 严格小于 $\text{mid}$ 的回路
如果存在，那么尝试 $[l, r] \leftarrow [l, mid]$，否则 $[l, r] \leftarrow [mid, r]$

难点在于 $\text{check}(mid)$ 的实现，如果存在平均权值严格小于 $mid$ 的回路
那么有

$$\begin{gathered} w_1 + w_2 + \cdots + w_m < m \cdot mid \\ (w_1 - mid) + (w_2 - mid) + \cdots + (w_m - mid) < 0 \end{gathered}$$

实现的时候，尝试修改边权 $w_i \leftarrow (w_i - mid)$，然后判断是否存在负圈即可

const int maxn = 100 + 10, maxm = 2e5 + 10;
const double eps = 1e-3;
const int inf = 0x3f3f3f3f;
int n, m;

namespace Graph {
    int idx = 1;
    int ver[maxm], ne[maxm], h[maxn];
    double e[maxm];

    void initG() {
        idx = 1;
        memset(h, 0, sizeof h);
    }
    void add(int a, int b, double c) {
        ver[++idx] = b, e[idx] = c, ne[idx] = h[a], h[a] = idx;
    }
}

using namespace Graph;

vector<double> f(maxn, (double)inf);
vector<int> inq(maxn, 0), cnt(maxn, 0);
bool negaCycle(int s, vector<double> &f) {
    queue<int> q;
    fill(f.begin(), f.end(), (double)inf);
    fill(inq.begin(), inq.end(), 0), fill(cnt.begin(), cnt.end(), 0);
    
    f[s] = 0;
    for (int i = 1; i <= n; i++) q.push(i), inq[i] = 1;

    while (q.size()) {
        auto x = q.front(); q.pop(); inq[x] = 0;
        for (int i = h[x]; i; i = ne[i]) {
            int y = ver[i];
            if (f[y] > f[x] + e[i] + eps) {
                f[y] = f[x] + e[i];
                if (!inq[y]) {
                    inq[y] = 1, q.push(y);
                    if (++cnt[y] > n) return true;
                }
            }
        }
    }
    return false;
}

bool check(double x) {
    for (int i = 2; i <= idx; i++) e[i] -= x;
    bool ret = negaCycle(1, f);
    for (int i = 2; i <= idx; i++) e[i] += x;
    return ret;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;

    int kase = 0;
    while (cas--) {
        printf("Case #%d: ", ++kase);

        scanf("%d%d", &n, &m);
        init(), initG();

        double mx = 0.0;
        while (m--) {
            int a, b;
            double c;
            scanf("%d%d%lf", &a, &b, &c);
            add(a, b, c), mx = max(mx, c);
        }

        if (check(mx + 1.0) == false) {
            printf("No cycle found.\n");
            continue;
        }

        double l = 0.0, r = mx;
        while (r - l > eps) {
            double mid = (l + r) / 2.0;
            if (check(mid)) r = mid;
            else l = mid;
        }
        printf("%.2lf\n", l);
    }
}

差分约束

差分约束系统，包含 $n$ 个变量 $\{x_1, x_2, \cdots, x_n\}$ 以及 $m$ 个约束条件
每个约束条件为 $\forall i, j, \ 1\leqslant i, j \leqslant n, \ \forall k, 1\leqslant k \leqslant m$

$$x_i - x_j \leqslant c_k$$

对于条件 $x_i - x_j \leqslant c_k$，变形为 $x_i \leqslant x_j + c_k$
如果从 $j \to i$ 连一条有向边，并且边的权值为 $c_k$，此时如果差分约束 $x_i - x_j \leqslant c_k$ 有解
那么边 $(j, i)$ 一定是松弛的

引理，如果 $(x_1, x_2, \cdots x_n)$ 为差分约束系统的一个可行解，那么 $(x_1+d, x_2+d, \cdots, x_n+d)$
也是差分约束系统的一个解

如果差分约束系统有解，那么令 $d = -\infty$，此时 $x_i + d < 0$，即 $x_i \leqslant 0$ 也是一个可行解
于是，如果差分约束系统有可行解，可以令 $x_0 = 0$，这样对于 $\forall i, \ x_i - x_0 \leqslant 0$
可以构造出一个约束图，建一个编号为 $0$ 的超级源点 $s$
并且令 $x_0 = f(0) = 0$，其中 $f$ 为最短路求解中的距离数组
从 $0$ 出发向图中所有的点 $i$ 连边，边的权值为 $0$

结论，如果差分约束系统有解，一个可行解为 $(x_1, x_2, \cdots, x_n) = (f(1), f(2), \cdots, f(n))$
其中 $f(i)$ 为从 $0 \to i$ 的单源最短路径
如果约束图 $G$ 中有负环，那么差分约束系统没有可行解

• $\{f(1), f(2), \cdots f(n)\}$ 是差分约束系统的一个可行解，因为此时任意的点都满足路径松弛
  $f(i) \leqslant f(j) + w(j, i)$，其中 $w(j, i) = c_k$
• $G$ 中执行 $\text{bellman ford}$ 存在负环，那么差分约束系统没有可行解
  下面用反正法，不妨设负环上点编号为 $\{u_1, u_2, \cdots, u_k\}$，那么此时如果存在可行解，对应有
  $x_2 - x_1 \leqslant c_1, \ x_3 - x_2 \leqslant c_2 \ \cdots, \ x_k - x_{k-1} \leqslant c_k$
  对不等式求和，此时有
  $x_k - x_1 \leqslant \sum c$，由于是环路，所以 $1$ 和 $k$ 实际上是一个点，那么 $x_k = x_1$
  也就是说，此时有 $0 \leqslant \sum c$，与该路径是负环矛盾

算法实现

• 对于每一个不等式 $x_j - x_i \leqslant c_k$，新建一条边 $\text{add}(i, j, c_k)$
  有向，$i \to j$，权值为 $c_k$
• 添加一个超级源点 $s = 0$，和其他所有点连一条边，权值为 $0$
• 从 $s$ 开始执行 $\text{bellman ford}$ 算法，如果有负环，那么差分约束系统无解
  否则 $x_i = f(i)$ 就是一个可行解，其中 $f$ 为最短距离数组

Halum 操作

由于权值的增加过程是相互独立的，对于点 $u$
令 $S(u)$ 为增加在 $u$ 这个点上的所有 $d$ 的和，问边的最小值非负且尽量大

可以二分最小值 $x$，如果满足 $\text{check}$ 所有边的权值 $\geqslant x$，尝试增大 $x$
问题就是 $\text{check}(x)$ 如何写

$\text{check}(x)$ 为 $\text{true}$，等价于对于所有边 $(u, v)$
$S(u) - S(v) + w(u, v) \geqslant x$，此时 $x, w(u, v)$ 确定，问题转换为是否存在合法的 $S(u), S(v)$，使得
$S(v) - S(u) \leqslant w(u, v) - x$，这可以用差分约束来解决

在原图的基础上，添加一个超级源点 $S$，这个超级源点到所有点 $u$ 连边，权值为 $0$
遍历每一条边 $(u, v) \in E$，尝试将这条边的权值 $-x$，并且执行 $\text{spfa}$ 判负环
如果有负环，$\text{check}(x)$ 返回 $\text{false}$ 并且减小 $x$

拆点与拆边

Steam Roller

由于存在方向，以及一条道路不能反复加倍，所以考虑拆点
对每个点 $(r, c)$ 拆成 $8$ 个点 $(r, c, dir, db)$
其中 $dir$ 表示这条边的方向，$db$ 表示这条边是否被加倍
$mp(r, c, dir, db)$ 表示状态哈希

这样我们可以暴力枚举每一个状态转移
$dir$ 表示当状态的方向，$ndir$ 表示下一个状态的方向，$db$ 表示当前边是否被加倍
$\forall dir, ndir \in [0, 3], \ \forall db, ndb \in [0, 1]$，暴力枚举状态转移
$(r, c, dir, db) \longrightarrow (nr, nc, ndir, ndb)$
构图之后用 $\text{dijkstra}$ 单源最短路解决

接下来就是编程实现的一些细节，保存路径的时候，我们需要判断从 $(r, c)$ 出发沿着 $dir$ 能否走的通
我们保存的是从 $u$ 出发的边 $(u \longrightarrow)$
存储状态时候，$(u, dir)$ 表示从 $dir$ 方向走进 $u$ 节点，即 $(\longrightarrow u)$
需要写 $\text{valid}(r, c, dir)$ 判断，问题是终点的状态是什么？
我们还需要一个状态，表示沿着 $dir$ 到达这个点 $(r, c)$，此时状态是否合法
这时候我们需要拆边了，以向左为例，此时 $dir = 0$，那么向右记为 $\text{inv}(dir)$
输入的时候，令 $g(r, c, dir) = g(r, c+1, \text{inv}(dir)) = \text{read}()$
这样在终点的时候，只需要处理 $\text{valid}(r2, c2, \text{inv}(dir)) = \text{true}$ 的状态

接着考虑 $\text{db}$ 加倍的问题，需要在可以加倍的时候，立刻加倍（即 $ndir \neq dir$ 时）
然后看一看上一次的边加倍了没？

if (ndir != dir) {
    // 此时新边肯定必须加倍，立刻加倍
    v += g(r, c, ndir);
    // 再看一下上一条边有没有漏加倍了？
    if (!db == 0) v += g(r, c, inv[dir])
}

最后用状态哈希，在 $(r, c, dir, db), (nr, nc, ndir, ndb)$ 连一条权值为 $v$ 的边

初始阶段，建立一个超级源点 $S = 0$，之后的状态，需要枚举 $4$ 个方向，如果
$g(r1, c1, dir) > 0$，那么从 $(r1, c1)$ 往 $dir$ 可以走的通，并且我们让边权立刻加倍
$r = r1 + dr(dir), \quad c = c1 + dc(dir)$
也就是说，从 $S$ 向 $(r, c, dir, 1)$ 连一条权值为 $2\cdot g(r1, c1, dir)$ 的边

然后枚举所有可能的状态 $(r, c, dir, db)$，首先我们要判断当前状态是否合法
实际上就是判断当前状态能否到达，也就是 $\text{valid}(r, c, \text{inv}(dir))$
然后枚举 $4$ 个方向 $\text{ndir}$，并且判断从 $(r, c)$ 能否走到 $(nr, nc)$
也就是 $\text{valid}(r, c, \text{ndir})$，如果可以走，那么按以上分析
从 $(r, c, dir, db) \to (nr, nc, ndir, ndb)$ 连边

这里还必须注意，储存状态的时候我们存的是前向弧 $(\longrightarrow u)$
但是拆边的时候，判断一条边可以不可以走，我们用的是 $(u \longrightarrow)$
所以对应关系是 $(r, c, dir, db) \Leftrightarrow g(r, c, \text{inv}(dir))$

拆点技巧

本例的拆点技巧很常用，点的状态用前向弧 $(dir, u)$ 表示
而从一个点出发的边用 $g(u, dir)$ 表示，双向边成对存储
输入边 $x = (u, v)$ 的时候，实际上输入 $g(u, dir) = g(v, \text{inv}(dir)) = x$
这样一个状态 $(dir, u)$ 是合法状态，当且仅当 $g(u, \text{inv}(dir)) \neq 0$

Low Cost Air Travel
一种很显然地构图方式，是暴力枚举每一张票，然后判断用这张票 $i$，能够经过的城市 $(u, v)$
$e(u, v) = \displaystyle\min_{i}(\text{cost}(i))$

但这种构图方式并不正确，因为规定每一张票必须从头坐，也就是说只能用它的一个前缀
也就是说对于票 $A \to B \to C$，此时从 $B \to C$ 不能用这张票，$B \to C$ 路径不存在

此时考虑给状态增加维度，注意到行程单 $\text{list}$ 上所有的点必须走完，考虑公共子序列的状态表示
对于行程单 $\text{list}[1\cdots n]$，用 $i \in [1, n]$ 表示当前完成行程单上第 $i$ 个位置（作为阶段）
此时人在城市 $P$，这时候的状态为 $(i, P)$

这样就可以枚举 $i \in \text{list}[1, n]$，并且枚举每一张票 $\forall k, \ \text{t}(k)$
注意到每一张票必须从头开始坐，对于第 $k$ 张票 $t(k)$，所经过的城市为
$t(k, 0), t(k, 1), \cdots, t(k, m)$，票价为 $\text{cost}(k)$
那么从 $s = (i, t(k, 0))$ 依次向 $(\cdots, t(k, p))$ 连一条权值为 $\text{cost}(k)$ 的边

具体是如何连？先令 $j \leftarrow i$
对于 $\forall p \in [1, m]$，此时用票 $k$ 经过了城市 $t(k, p)$
如果 $t(k, p) = \text{list}(j)$，那么 $j \leftarrow j+1$ （当然还必须满足 $j < n$）
此时从 $s = (i, t(k, 0))$ 向 $(j, t(k, p))$ 连一条权值为 $\text{cost}(k)$ 的边
实际上类似动态规划，我们处理 $i \to i+1$ 阶段的转移

在执行最短路的时候，行程清单为 $\text{list}[0\cdots n-1]$
源点为 $S = (0, \text{list}(0))$，终点为 $T = (n-1, \text{list}(n-1))$

Flying to Fredericton

由于有最大停留次数 $\leqslant s$ 的限制，所以考虑拆点，将 $n$ 个点拆成 $100 \cdot n$ 个点
其中 $(k, u)$ 状态表示到达 $u$ 之前已经停留了 $k$ 次
对于每一条边 $(u, v, w)$，枚举停留次数 $i \in [0, n]$
连边 $(i, u) \to (i+1, v)$，权值为 $w$，源点为 $S = (0, \text{Calgary})$
求单源最短路，最后的答案为 $\forall i \in [1, 1+s], \ \min((i, \text{Fredericton}))$

平面图转最短路

有一些问题是经典的

Animal Run
如果把平面图中的点看成图的节点，横线和竖线看成边，那么问题转换为一个经典的最小割模型
但 $n * m = 10^6$，用最大流算法无法求解

如图所示，假设将图中左上角看作起点，右下角看作终点，要想成功拦截
那么切割边必须满足一定的条件，比如说从左边界连到上边界，不难写出以下几种可行切割
$(\text{left}, \text{up}), \ (\text{left}, \text{right}), \ (\text{down}, \text{right}), \ (\text{down}, \text{up})$

于是可以考虑状态建图，将每一条边压缩成一个点 $u(i, j, fl)$
点的权值为原先这条边的权值 $w(u) = w(i, j, fl)$
其中 $i, j$ 表示边的坐标，$fl$ 表示边的种类，即横线，竖线，还是斜线
另外为了处理边的代价以及边界问题，添加一个超级源点 $S$
每一条边实际上是用前向弧表示，也就是说，在状态图中添加边 $(u, v)$ 时候
$e(u, v) = w(v)$，添加超级源点时，实际上加入边 $(S, s, w(s))$

这样可以设计出如下算法

• 对每一组三角形内的三条边 $u(i, j, fl)$，两两连边
  编程实现的时候，可以把一个三角形看成一个单位 $\text{vector}$，里面有 $3$ 个节点（边）
  两两相连来建图
• 添加一个超级源点 $S$，由于合法切割起点是左边界和下边界
  所以从 $S$ 向这些点 $u$ 连边 $(S, u)$，边的权值为 $w(u)$
  接着从 $S$ 开始执行单源最短路即可，左右解为右边界和上边界所有道路的最小值

矩阵运算与最短路

Dice Contest

骰子旋转问题的状态表示
如上图所示，骰子的标准姿态为 $P = \{0, 1, 2, 3, 4, 5\}$，这里的数值表示下标
以向上旋转为例，新姿态为 $P_2$，那么此时 $P(0) \Leftrightarrow P_2(2)$
即原来下标为 $0$ 的数，在新姿态下，位于下标 $2$ 处，写成矩阵运算 $\bm{T}$ 的作用
$P(0) \Leftrightarrow P_2(2) = \bm{T}(P(0))$，用一维数组表示为 $\bm{T}(0) = 2$
以此类推，向上旋转的矩阵变换为 $\bm{T} = \{2, 1, 5, 0, 4, 3\}$
这样枚举姿态的时候，$P_2(i) = \bm{T}(P(i))$ 即可实现

vector<int> dice24[24]

以上就可以封装出骰子所有的姿态，这样在编程实现的时候，我们枚举骰子的姿态 $i \in [0, 24)$
表示骰子处于姿态 $i$，那么此时骰子第 $j$ 表面上的数为多少呢？
假设骰子原来第 $j$ 表面的数为 $A[j]$，执行 $B(\text{dice24}[i][j]) \leftarrow A[j]$
对 $B$ 按以上映射染色，这样我们就可以得到旋转之后，骰子每个面的数值

回到该问题
如果 $x$ 不是无限大，那么该问题就是一个标准的隐式图最短路，每一个位置 $(x, y)$ 有 $24$ 种状态
根据 $(x, y, \text{dice24})$ 来建图，然后暴力枚举 $24$ 种状态之间的合法转移（即上下左右翻转）
求一遍最短路，终点为 $(x_2, y_2)$，最后 $\displaystyle\min_{k \in [0, 24)}(x, y, \text{dice24}(k))$ 就是答案

但由于 $x$ 太大，以上算法无法通过，借助动态规划和矩阵变换的思想，仍然可以找到突破口
因为骰子的姿态只有 $24$ 种，并且 $y \in [0, 4)$ 范围也很小
也就是说，对于第 $i$ 列而言，它总共的姿态才 $24 \cdot 4 = 96$ 种
来看看从第 $i$ 列到第 $i+1$ 列骰子的姿态是如何变化的？

骰子从 $i$ 列走到 $i+1$，一种走法是向右翻转，有可能此时的代价太大
一种更优的策略是先向左翻转，然后向上，再向右，再向下
不妨假设骰子在第 $x$ 列，姿态为 $i$，想要走到第 $x+1$ 列，目标姿态为 $j$
那么存在中间的过渡姿态 $k$，使得 $i \to k_1 \cdots \to k_m \to j$ 更优

$x \to x+1$ 转移的时候，可以枚举 $x$ 位置所有的 $96$ 种姿态 $u$，对于每一种姿态
挨个求一遍单源最短路 $\text{dijkstra}(u)$，得到距离向量 $f$
此时 $v \in [0, 96)$ 对应 $x+1$ 的 $96$ 种姿态，由此可以构造出完全图
$\bm{M}(u, v) = f(v)$

到了这里，问题解法就呼之欲出了，以上方法我们可以得到一个 $96 \times 96$ 的完全图 $\bm{M}$
$\text{floyd}$ 算法中有一个结论，完全图 $\bm{A}$ 中 $s \to t$ 恰好经过 $n$ 条边的最短路为 $\bm{A}^n(s, t)$
借鉴这个思路，$x$ 列骰子的姿态为 $i$，$x+1$ 列骰子姿态为 $j$
那么姿态 $i \to j$ 转移的最小代价为 $\bm{M}(i, j)$
$x \to x+1 \to x+2$ 呢？假设 $x$ 列姿态为 $i$，状态压缩为 $(x, i)$，第 $x+2$ 列姿态为 $j$，压缩为 $(x+2, j)$
$(x, i)$ 到 $(x+2, j)$ 转移的最小代价不妨记为 $\bm{M}_2(i, j)$
枚举 $x+1$ 列的姿态 $k$，那么 $\bm{M}_2(i, j) = \displaystyle \min_{k \in [0, 96)} \left(\bm{M}(i, k) + \bm{M}(k, j) \right)$

令 $d = |x_2 - x_1|$，假设起点 $x_1$ 处姿态为 $i$，终点 $x_2$ 处姿态为 $j$，那么
$(x_1, i) \to (x_2, j)$ 的最小代价为 $\bm{M}^d$，这可以用矩阵快速幂求解

算法设计，建图
将骰子所有姿态预处理出来，并用一个 $\text{vector}$ 保存，不妨设为 $\text{dice24}(\cdots)$
状态压缩，举个例子，假设当前在 $x$ 位置，$y$ 列，骰子的姿态为 $\text{dice24}(i) = \{0, 1, 2, 3, 4, 5\}$
当前状态为 $(x, y, \text{dice24}(i))$

枚举所有可能的状态并建图，为了能把骰子所有状态都枚举到
一开始的时候要建立一个 $X \times Y$ 区域，$Y$ 题目规定为 $4$，$X$ 呢？
由于骰子水平翻转 $4$ 次就会回到原来姿态，可以令 $X = 10$，这样一定能够把所有姿态都枚举到
$\forall x \in [0, X), \ \forall y \in [0, 4), \forall i \in [0, 24)$，对于每一种状态 $(x, y, \text{dice24}(i))$
要处理以下几个细节

先是费用计算，按前面所说的，先对 $\text{dice24}(i)$ 进行“染色”，即枚举 $j \in [0, 6)$ 个面，骰子标准姿态设为 $A(j)$
$B(\text{dice24}(i, j)) = A(j)$，则此时 $w = B[0]$ 就是翻转后朝上的面的数值，即翻转代价

每一种状态 $(x, y, \text{dice24}(i))$，尝试前后左右 $4$ 个方向
这里需要一个 $\textbf{rot}(dir, \text{dice24}(i))$ 函数，计算出旋转后相对应的姿态 $\text{dice24}(ni)$
根据 $\text{dice24}(ni)$ 计算出翻转代价 $w$
$(x, y, \text{dice24}(i))$ 到 $(nx, ny, \text{dice24}(ni))$ 之间连一条权值为 $w$ 的边

最短路与矩阵快速幂
初始状态是已知的，令 $x \leftarrow \displaystyle\frac{X}{2}$，$y$ 为给定值
$d = |x_1 - x_2|$ 为始末状态 $x$ 坐标的差，标准姿态 $\bm{A} = \{0, 1, 2, 3, 4, 5\}$
则初始状态为 $S(x, y, \bm{A})$

执行 $\text{dijkstra}(S)$ 并且得到距离向量 $f$，$f(u)$ 表示从 $S \to u$ 的最短路径
$f(u) \neq +\infty$ 的状态 $u$，就是从 $S$ 可达的状态
这里如果对状态 $(x, y, \bm{dice24})$ 设计哈希函数 $\text{get} = 96 \cdot x + \text{hash}(y, \bm{dice24})$
就可以枚举所有 $96$ 种可能的状态 $\forall y \in [0, 4), \bm{i} \in [0, 24)$，令 $u = \textbf{get}(x, y, \bm{i})$
将 $\text{dijkstra}$ 可达状态的最短路径保存下来，$\bm{g}(\text{mp}[(y, \bm{i})]) \leftarrow f(u)$ 即可

说明，$u(x, y, \bm{dice24})$ 为三元组，实际上我们并不需要 $x$ 这个维度的信息
$(y, \bm{dice24})$ 才是我们关注的，用一个 $\text{mp}$ 将 $(y, \bm{dice24})$ 映射到哈希值

接下来构造 $96 \times 96$ 的完全图矩阵，用来表示任意两个姿态 $i, j$ 间转移的代价
枚举骰子的姿态 $\bm{i}$ 和 $\bm{j}$，对于姿态 $\bm{i} \to \bm{j}$ 的变换，构造邻接矩阵
简单来说，分别从每个起始姿态 $\bm{i}$ 开始执行 $\text{dijkstra}$，看看它能够到达哪些姿态
可达的姿态不妨记为 $j$，可以根据 $\text{dijkstra}$ 的距离向量 $f$，构造 $\bm{M}(i, j) = f(j)$

具体来说，每一个起始状态 $u = (x, y, \bm{i})$ 对应 $96$ 种姿态中的 $\bm{uu}(y, \bm{i})$
每个起始状态都执行 $\text{dijkstra}(u)$，然后扫描每一个终点状态
终点状态为 $v = (x+1, y2, \bm{j})$，同样对应 $96$ 种姿态中的 $\bm{vv}(y2, \bm{j})$
$\bm{M}(\bm{uu}, \bm{vv}) = f(v)$

执行矩阵快速幂，答案为 $\forall i \in [0, 96), \forall j \in [0, 96)$
$\displaystyle \min \left(\bm{g}(i) + \bm{M}^{d}(i, j) \right)$
注意这里 $j$ 状态必须合法，$j$ 压缩了状态 $(y, \bm{dice24})$，用一个 $\text{map}$ 映射即可解决
只有当 $\text{mp}(j).y = Y2$ 时，才合法 （$Y2$ 是终点的纵坐标）

骰子旋转与染色

以图中为例子，往上翻转为例子，关注下标

• 往上翻转，侧面不变，$1 \to 1, \ 4 \to 4$
• 其他面下标变化 $0 \to 2, \ 2 \to 5 \ 5 \to 3, \ 3 \to 0$

const vector<int> up = {2, 1, 5, 0, 4, 3};

inline void rot(const vector<int> &T, vector<int> &p) {
    vector<int> q = p;
    for (int i = 0; i < 6; i++) p[i] = T[q[i]];
}

inline vector<int> paint(const vector<int> &dice, const vector<int> &p) {
    vector<int> res = p;
    for (int i = 0; i < 6; i++) res[dice[i]] = p[i];
    return res;
}

骰子枚举所有姿态的代码
具体来说，就是从 ${0, 1, 2, 3, 4, 5}$ 中任意选一个数转到顶面或者正面
然后这个面不动，左右依次翻转 $3$ 次，就可以打表出所有姿态了
下面的例子是 dice contest 问题中的骰子

void getDice24() {
    const vector<int> p0 = {0, 1, 2, 3, 4, 5};
    for (int i = 0; i < 6; i++) {
        //  in face
        vector<int> p = p0;
        if (i == 0) {
            rot(rdown, p);
        }
        if (i == 2) {
            rot(rri, p), rot(rdown, p);
        }
        if (i == 3) {
            rot(rle, p), rot(rdown, p);
        }
        if (i == 4) {
            rot(rdown, p), rot(rdown, p);
        }
        if (i == 5) {
            rot(rup, p);
        }

        _for(_, 0, 4) {
            printf("{%d, %d, %d, %d, %d, %d},\n", p[0], p[1], p[2], p[3], p[4], p[5]);
            rot(rle, p);
        }
    }
}

最长路与正环

$\text{bellman ford}$ 算法不仅可以用来求最短路，如果将松弛方程改为
$d(y) < d(x) + e(x, y), \ d(y) = d(x) + e(x, y)$
统计点 $u$ 入队次数，如果 $\text{cnt}(u) > n$ 那么就有正环

Tomato Automata

因为循环的处理比较复杂，先来看没有循环语句的情况
如果没有循环语句，那么其他语句构成了链式结构，如果从 $u$ 语句跳转到 $v$ 语句
可以用单向链表来存储，判环可以用快慢指针，如果没有环，就看走到 $\text{die}$ 处要多少步

借助该思路，可以对程序语句建图，对于跳转语句，比如 $\text{Ifgo} \ v$
表示当前在 $u$ 行，跳转到 $v$ 行，用前向弧的方法来加边
此时在 $(u, v)$ 间添加权值为 $1$ 的边，表示从 $u$ 到达 $v$ 需要多执行 $1$ 步程序
那么 $\text{loop} \ s \ x$ 呢？即从 $s \to u$ 循环 $x$ 次
那么需要高效统计出 $(s \to u)$ 一共执行了多少句语句 $sum$

进一步考虑该问题
题目中要求循环严格嵌套，并且不能从循环内部跳到循环外部
程序能停机，程序语句必须构成一个有向无环图，先简单地根据程序语句建一张图
然后判断这张图是否为 DAG，可以用 tarjan 的 dfs 来判断

void dfs(int u, int fa, int &fl) {
    vis[u] = 1;
    for (auto v : G[u]) {
        if (vis[v] == 1) {
            fl = 1;
            continue;
        }

        // 处理其他信息
 
        if (vis[v] == 0) dfs(v, u, fl);
    }
    vis[u] = 2;
}

对于语句 $\text{Ifgo} \ x$ 有两种选择，一种是跳到 $x$ 行，另一种是执行下一行
假设当前行为 $i$，$\text{Ifgo} \ x$ 语句，$(i, x), (i, i+1)$ 都要连边
$\text{loop}$ 语句，$(i, i+1)$ 要连边，由于不能从循环内部跳到外部
如果有死循环一定是循环内部有环，这一点可以构建完 DAG 之后先判环

具体来说，执行 dfs 判断有向图是否为 DAG，在 dfs 的同时维护有关信息
对于 dfs 的树边 $(u, v)$，（即 dfs 的一个分支），此时程序语句从 $u$ 执行到 $v$
一定会多执行一条语句，在最终的新图 $G$ 中加边 $\text{add}(u, v, 1)$
考虑到会有多条 $\text{die}$ 语句，可以新建一个超级汇点 $T$，$\text{add}(\text{die}, T, 0)$

循环语句 $\text{loop} \ p \ x$，表示从 $p$ 行到当前行 $i$，多执行 $x-1$ 次
这取决于 $p \to i$ 之间有多少条语句
注意到我们在新图 $G$ 中已经离线保存程序相邻两步 $u \to v$ 需要执行多少条语句
可以采用一边 $\text{spfa}$ 一边维护的方法，具体来说
如果当前语句 $u$ 是循环语句，那么 $(u, v)$ 需要在原来的基础上多执行循环的部分
循环部分的总语句数是 $(x-1) \cdot \Delta$，只需要在线修改 $(u, v)$ 的权值，增加 $(x-1) \cdot \Delta$
而 $\text{spfa}$ 的距离向量 $f(i)$ 恰好表示从第一条语句到第 $i$ 条语句，一共执行的语句数量
所以 $\Delta = (f(i) - f(p) + 1)$

综上，执行 $\text{spfa}(1)$，对于边 $(u, v), \ w = e(u, v)$，特别地，如果 $u$ 为循环语句
$w += (f(u) - f(p) + 1) \cdot (x-1)$，执行松弛 $f(y) = \max (f(y), f(x) + w)$
初始化 $f(1) = 1$，因为第一条语句总会执行，建立一个超级汇点 $T$，答案为 $f(T)$