Bellman-Ford 负环

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

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

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

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

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

w1+w2++wm<mmid(w1mid)+(w2mid)++(wmmid)<0\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}

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

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
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);
}
}

差分约束

差分约束系统,包含nn 个变量{x1,x2,,xn}\{x_1, x_2, \cdots, x_n\} 以及mm 个约束条件
每个约束条件为i,j, 1i,jn, k,1km\forall i, j, \ 1\leqslant i, j \leqslant n, \ \forall k, 1\leqslant k \leqslant m

xixjckx_i - x_j \leqslant c_k

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

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

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

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

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

算法实现

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

Halum 操作

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

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

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

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

拆点与拆边

Steam Roller

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

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

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

接着考虑db\text{db} 加倍的问题,需要在可以加倍的时候,立刻加倍(即ndirdirndir \neq dir 时)
然后看一看上一次的边加倍了没?

1
2
3
4
5
6
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)(r, c, dir, db), (nr, nc, ndir, ndb) 连一条权值为vv 的边

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

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

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

拆点技巧

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

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

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

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

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

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

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

Flying to Fredericton

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

平面图转最短路

有一些问题是经典的

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

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

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

这样可以设计出如下算法

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

矩阵运算与最短路

Dice Contest
dice-contest

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

1
vector<int> dice24[24]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

骰子旋转与染色

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

  • 往上翻转,侧面不变,11, 441 \to 1, \ 4 \to 4
  • 其他面下标变化02, 25 53, 300 \to 2, \ 2 \to 5 \ 5 \to 3, \ 3 \to 0
1
2
3
4
5
6
7
8
9
10
11
12
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{0, 1, 2, 3, 4, 5} 中任意选一个数转到顶面或者正面
然后这个面不动,左右依次翻转33 次,就可以打表出所有姿态了
下面的例子是 dice contest 问题中的骰子

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
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);
}
}
}

最长路与正环

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

Tomato Automata

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

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

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

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

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