floyd 任意两点最短路径

floyd 算法能够求出任意两点(i,j)(i, j) 之间的最短路径
根据动态规划的思想,对编号为kk 这个节点,我们有两种决策,选还是不选这个点
由此根据考虑编号为kk 的节点作为 dp 的阶段,从k1k-1kk 的转移
需要决策是否经过编号为kk 的节点

f(k,i,j)=min(f(k1,i,j),f(k1,i,k)+f(k1,k,j))f(k, i, j) = \min (f(k-1, i, j), f(k-1, i, k) + f(k-1, k, j))

如果用邻接矩阵存图,A(i,j)A(i, j) 表示边(i,j)(i, j) 的长度,那么 dp 初始化为
f(0,i,j)=A(i,j)f(0, i, j) = A(i, j)

传递闭包

不妨用f(i,j)=1f(i, j) = 1 表示iijj 之间有关系f(i,j)=0f(i, j) = 0 表示没有关系
特别地,f(i,i)=1f(i, i) = 1,可以用 floyd 算法解决传递闭包问题

1
2
3
4
5
6
7
8
9
10
11
const int maxn = 1e3 + 10;
bool f[maxn][maxn];
int n;
int main() {
// ...
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] |= (f[i][k] & f[k][j]);
// ...
}

Sorting It All Out

很显然这是一个有向图传递闭包的问题,对于i<ji < j 的不等式,令f(i,j)=1f(i, j) = 1
i>ji > j 转为j<ij < i 处理,令f(j,i)=1f(j, i) = 1

执行 floyd 传递闭包,如果存在f(i,j)=1f(i, j) = 1 并且f(j,i)=1f(j, i) = 1,那么不等式存在矛盾
如果f(i,j)=0f(i, j) = 0 并且f(j,i)=0f(j, i) = 0 说明(i,j)(i, j) 之间的大小关系不确定
此外如果f(i,j), f(j,i)f(i, j), \ f(j, i) 仅有一个为11,那么能够确定变量之间的大小关系

需要输出不等式之间的大小关系,由于是一个 DAG,可以考虑使用拓扑排序输出

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
const int maxn = 26 + 10;
int G[maxn][maxn], f[maxn][maxn], deg[maxn];
int n, m;

void floyd() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
f[i][j] |= (f[i][k] & f[k][j]);
}
}
}

int conflict() {
for (int i = 0; i < n; i++) {
if (f[i][i]) return 1;
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (f[i][j] && f[j][i]) return 1;
}
}
return 0;
}

int sure() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (f[i][j] == 0 && f[j][i] == 0) return 0;
}
}
return 1;
}

void topo() {
queue<int> que;
string res = "";
for (int i = 0; i < n; i++) if (deg[i] == 0) que.push(i);

while (que.size()) {
auto u = que.front(); que.pop();
res += ('A' + u);

for (int v = 0; v < n; v++) if (G[u][v] && --deg[v] == 0) que.push(v);
}
printf("%s", res.c_str());
printf(".\n");
}

void init() {
memset(G, 0, sizeof G);
memset(f, 0, sizeof f);
memset(deg, 0, sizeof deg);
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2 && n) {
init();

int st = 0, t = 0;
// -1 conflict, 1 ok, 0 not sure

for (int i = 0; i < m; i++) {
char str[10];
scanf("%s", str);

if (st != 0) continue;

int u = str[0] - 'A', v = str[strlen(str)-1] - 'A';
f[u][v] |= 1, G[u][v] = 1, deg[v]++;

floyd();

if (conflict()) st = -1;
else if (sure()) st = 1;
t = i;
}

// get ans
if (st == -1) printf("Inconsistency found after %d relations.\n", t+1);
else if (st == 1) {
printf("Sorted sequence determined after %d relations: ", t+1);
topo();
}
else puts("Sorted sequence cannot be determined.");
}
}

无向图最小环

Acwing344

Sightseeing Trip

同样套用 floyd 算法
在第kk 个阶段,f(i,j)f(i, j) 表示编号为{0k1}\{0\cdots k-1\} 节点集合中
(i,j)(i, j) 之间的最短路,用min(f(i,j)+e(i,k)+e(k,j),res)\min(f(i,j) + e(i, k) + e(k, j), res) 更新答案resres

然后再将kk 这个点纳入集合中,用floyd\textbf{floyd} 算法更新f(i,j)f(i, j) 的最短路径
f(i,j)f(i, j) 更新完之后,就考虑了{0k}\{0\cdots k\} 节点集合的最短路

继续往下迭代,即可得到最优解

特别注意的是,如图中所示,i,ji, j 两个节点的编号<k< k

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
const int maxn = 200 + 10, inf = 0x3f3f3f3f;
int n, m;
int e[maxn][maxn], f[maxn][maxn], res = inf;
int pos[maxn][maxn];

vector<int> path;

void get_path(int x, int y) {
if (pos[x][y] == 0) return;
int k = pos[x][y];

get_path(x, k);
path.push_back(k);
get_path(k, y);
}

void floyd() {
memcpy(f, e, sizeof e);
memset(pos, 0, sizeof pos);
res = inf;
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++) for (int j = i+1; j < k; j++) {
if ((ll)f[i][j] + e[j][k] + e[k][i] < res) {
res = f[i][j] + e[j][k] + e[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 (f[i][k] + f[k][j] < f[i][j]) {
f[i][j] = f[i][k] + f[k][j];
pos[i][j] = k;
}
}
}
}

void init() {
memset(e, inf, sizeof e);
for (int i = 0; i <= n; i++) e[i][i] = 0;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

init();
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u][v] = e[v][u] = min(e[u][v], w);
}

// then solve

floyd();
if (res == inf) puts("No solution.");
else {
for (auto x : path) printf("%d ", x);
printf("\n");
}
}

floyd 与广义矩阵运算

给定一张无向图,求从起点到终点恰好经过nn 条边(可以重复经过)的最短路

在 floyd 算法执行过程中,最开始阶段A1(i,j)=e(i,j)A_1(i, j) = e(i, j),即表示iji \to j 仅经过一条边(i,j)(i, j) 的最短路
而 floyd 方程中,A2(i,j)=min1kn{A1(i,k)+A1(k,j)}A_2(i, j) = \displaystyle\min_{1 \leqslant k \leqslant n} \{A_1(i, k) + A_1(k, j)\}
此时我们枚举了ikji \to k \to jA2(i,j)A_2(i, j) 表示iji \to j 经过了22 条边的最短路

以此类推,用Am(i,j)A_m(i, j) 表示恰好经过mm 条边的最短路,那么

Am+r(i,j)=min1kn{Am(i,k)+Ar(k,j)}A_{m+r}(i, j) = \min_{1 \leqslant k \leqslant n} \{A_{m}(i, k) + A_{r}(k, j)\}

最后答案是求An(s,t)A_n(s, t),可以用矩阵快速幂来求解,不过矩阵乘法的过程,需要改成

C(i,j)=min1kn{A(i,k)+B(k,j)}C(i, j) = \min_{1 \leqslant k \leqslant n} \{A(i, k) + B(k, j)\}

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
const int maxn = 100 + 10, inf = 0x3f3f3f3f;
map<int, int> M;
int n, N, m, s, t, G[maxn][maxn], idx = 0;

typedef vector<vector<int> > Matrix;

Matrix get_matrix() {
Matrix res(maxn, vector<int>(maxn, inf));
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
res[i][j] = G[i][j];
}
return res;
}

Matrix matrix_mul(const Matrix &A, const Matrix &B) {
Matrix res(maxn, vector<int>(maxn, inf));
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++)
res[i][j] = min(res[i][j], A[i][k] + B[k][j]);
}
return res;
}


void solve(Matrix &A) {
N--;
Matrix res = A;
for (; N; N >>= 1) {
if (N & 1) res = matrix_mul(res, A);
A = matrix_mul(A, A);
}
cout << res[M[s]][M[t]] << endl;
}

void init() {
M.clear();
memset(G, inf, sizeof G);
idx = 0;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &N, &m, &s, &t);
init();

// get data
for (int i = 0; i < m; i++) {
int x, y, z;
scanf("%d%d%d", &z, &x, &y);
int u = M[x] ? M[x] : (M[x] = ++idx);
int v = M[y] ? M[y] : (M[y] = ++idx);

G[u][v] = G[v][u] = z;
}
n = idx;
Matrix A = get_matrix();

solve(A);
}

最短路和 dp

Adventure Of Super Mario

类似背包问题,容易想到的是当前使用了kk 次魔法鞋,作为 dp 的一个状态维度
dp(v,k)dp(v, k) 表示当前位于节点vv 处,并且使用了kk 次魔法鞋,从起点到当前位置所耗费的最短时间

对于 k[0,K]\forall \ k \in [0, K],当前在节点vv 处,根据是否使用魔法鞋存在22 种状态转移
(u,v)(u, v) 的状态转移如下,其中uprev(v)u \in \text{prev}(v),在节点vv 的前驱节点集合中
u[1,v1]u \in [1, v-1]

  • dp(v,k)=minu[1,v1]{dp(u,k)+f(u,v)}dp(v, k) = \displaystyle \min_{u \in [1, v-1]} \{dp(u, k) + f(u, v)\},其中f(u,v)f(u, v) 一定是uvu\to v 的最短路径
    这可以通过 floyd 算法预处理来求出
  • dp(v,k)=minu[1,v1]{dp(u,k1)}dp(v, k) = \displaystyle \min_{u \in [1, v-1]} \{dp(u, k-1)\},约束条件为
    f(u,v)Lf(u, v) \leqslant L 并且(u,v)(u, v) 最短路径上的节点编号A\leqslant A
    最短路径上的节点编号不超过AA,正好可以用floyd\text{floyd} 算法
    floyd\text{floyd} 算法执行到kk 这个阶段并且完成f(i,j)=min(f(i,k)+f(k,j))f(i, j) = \min (f(i, k) + f(k, j)) 这个松弛操作的时候
    f(i,j)f(i, j) 表示(i,j)(i, j) 经过编号不超过kk 的节点的最短路径
    上述约束条件可以在 floyd 算法执行的时候求出,具体来说
    f(i,j)L and kAf(i, j) \leqslant L \ \textbf{and} \ k \leqslant A

最后考虑 dp 的初始状态和终点
初始状态,注意到状态表示dp(u,k)dp(u, k)22 个维度
k[0,K]:dp(s,k)=0\forall k \in [0, K]: \quad dp(s, k) = 0
uV:dp(u,0)=f(s,u)\forall u \in V: \quad dp(u, 0) = f(s, u)

最后的答案为mink[0,K]dp(t,k)\displaystyle\min_{k \in [0, K]} dp(t, k)

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
const int maxn = 100 + 10, inf = 0x3f3f3f3f;
int A, B, M, L, K, n, s, t;

int f[maxn][maxn];

void init() {
memset(f, inf, sizeof f);
n = A+B;
for (int i = 1; i <= n; i++) f[i][i] = 0;
s = 1, t = A+B;
}

int can[maxn][maxn];

void floyd() {
memset(can, 0, sizeof can);
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
if (f[i][j] > f[i][k] + f[k][j]) {
f[i][j] = f[i][k] + f[k][j];
}
if (k <= A && f[i][j] <= L) can[i][j] = 1;
}
}
}

int dp[maxn][maxn];
void solve() {
memset(dp, inf, sizeof dp);
for (int i = 0; i <= K; i++) dp[s][i] = 0;
for (int u = 1; u <= n; u++) dp[u][0] = f[s][u];

for (int v = 1; v <= n; v++) {
for (int k = 1; k <= K; k++) {
_for(u, 1, v) {
if (can[u][v]) dp[v][k] = min(dp[v][k], dp[u][k-1]);
dp[v][k] = min(dp[v][k], dp[u][k] + f[u][v]);
}
}
}
}

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

while (cas--) {
cin >> A >> B >> M >> L >> K;
init();

// get graph
for (int i = 0; i < M; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
f[x][y] = f[y][x] = min(f[x][y], z);
}

// floyd and dp

floyd();
solve();
int ans = inf;
for (int i = 0; i <= K; i++) ans = min(ans, dp[n][i]);
cout << ans << endl;
}
}

最短路建图:拆点

Full Tank?

要求从sts \to t 的最便宜路径,不难想到将油价作为边权,由于油箱容量c[0,C]c \in [0, C]
油箱容量cc 也应该作为状态维度
(u,c)(u, c) 二元组表示当前汽车在点uu 处,并且油箱有油cc 单位

对于当前点vv,根据在vv 处是否加油,存在22(u,v)(u, v) 的状态转移

  • (u, c+d(u,v))0(v,c)(u, \ c+d(u, v)) \xrightarrow{0} (v, c),此时c+d(u,v)Cc + d(u, v) \leqslant C
  • (v,c1)pv(v,c)(v, c-1) \xrightarrow{p_v} (v, c),在(v,c1)(v, c-1)(v,c)(v, c) 间连一条权值为pvp_v 的边
    实际上这里将vv 这个点拆成22 个状态,当然c10 and cCc-1 \geqslant 0 \ \textbf{and} \ c \leqslant C

这样可以以(s,0)(s, 0) 作为起点SS,执行dijkstra\text{dijkstra},求出单源最短路
u,c:d[(u,c)]\forall u, c: \quad d[(u, c)],最后答案就是minc[0,C]d(t,c)\displaystyle\min_{c \in [0, C]} d(t, c)

如果用哈希实现,将结构体作为keykey,代码如下

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
class A {
public:
int u, c;
A(int u = 0, int c = 0) : u(u), c(c) {}
bool operator< (const A &rhs) const {
return u < rhs.u || (u == rhs.u && c < rhs.c);
}
};

struct hashfun {
std::size_t operator() (const A &a) const {
return ( (hash<int>()(a.u))
^ (hash<int>()(a.c) << 1) );
}
};

struct eq {
bool operator() (const A &lhs, const A &rhs) const {
return lhs.u == rhs.u && lhs.c == rhs.c;
}
};

unordered_map<A, int, hashfun, eq> mp;

int get(const A &a) {
return mp[a] ? mp[a] : (mp[a] = ++n);
}

如果本例先建出隐式图,再进行dijkstra\text{dijkstra} 的话,每次都build\text{build} 会造成算法开销过大
实际上,我们在dijkstra\text{dijkstra} 的时候没有必要把整张图都建出来,因为有一些节点根本用不到
dijkstra\text{dijkstra} 的时候优先队列维护二元组(d[(u,c)],(u,c))(d[(u, c)], (u, c)),对于当前状态(u,c)(u, c)
检查 v: (u,v)E\forall \ v: \ (u, v) \in E,对于边v: (u,v)\forall v : \ (u, v),存在转移

  • (u,c)pu(u,c+1)(u, c) \xrightarrow{p_u} (u, c+1),当然c+1Cc+1 \leqslant C,此时转移的权值代价pup_u
  • (u,c)0(v,ce(u,v))(u, c) \xrightarrow{0} (v, c-e(u, v)),必须ce(u,v)0c-e(u, v) \geqslant 0,转移权值为00

起点为S=(s,0)S = (s, 0),最后的答案为
c: minc[0,C]d[(t,c)]\forall c: \ \displaystyle\min_{c \in [0, C]}d[(t, c)]
另外,由于dijkstra\text{dijkstra} 不会有负权边,所以取出二叉堆堆顶元素(u,c)(u, c),如果发现u=tu = t
那么应该立即结束dijkstra\text{dijkstra},不需要继续扩展了,后续点的代价dd 一定比d[(u,c)]d[(u, c)]
后续节点也用不到

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
const int maxn = 2e3 + 10, inf = 0x3f3f3f3f;
const int maxm = 2e4 + 10;

int n, m, C, s, t, p[maxn], res = inf;

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

void add(int x, int y, int z) {
ver[++idx] = y, e[idx] = z, ne[idx] = head[x], head[x] = idx;
}

void init() {
idx = 1;
memset(head, 0, sizeof head);
}
};

class A {
public:
int u, c;
A(int u, int c) : u(u), c(c) {}
bool operator< (const A &rhs) const {
return u < rhs.u || (u == rhs.u && c < rhs.c);
}
};

struct hashfun {
int operator() (const A &a) const {
return a.u * 1003 + a.c;
}
};

struct eqfun {
bool operator() (const A &lhs, const A &rhs) const {
return lhs.u == rhs.u && lhs.c == rhs.c;
}
};

unordered_map<A, int, hashfun, eqfun> mp;
int tot = 0;

inline int get(const A &a) {
return mp[a] ? mp[a] : (mp[a] = ++tot);
}

const int N = 1e5 + 10;
int d[N], vis[N];
typedef pair<int, A> PII;
// (d[ states ], (u, c))

void dijkstra() {
using namespace Graph;
memset(d, inf, sizeof d);
memset(vis, 0, sizeof vis);
res = inf;

priority_queue<PII, vector<PII>, greater<PII> > q;
int ss = get(A(s, 0));
d[ss] = 0;
q.push(PII(d[ss], A(s, 0)));

while (q.size()) {
int D = q.top().first;
auto x = q.top().second; q.pop();

if (x.u == t) {
res = min(res, D);
return;
}

int sx = get(x);
if (vis[sx]) continue;
vis[sx] = true;

if (x.c + 1 <= C) {
A y(x.u, x.c+1);
int sy = get(y);

if (d[sy] > D + p[x.u]) {
d[sy] = D + p[x.u];
q.push(PII(d[sy], y));
}
}

for (int i = head[x.u]; i; i = ne[i]) {
int v = ver[i];
if (x.c >= e[i]) {
A y(v, x.c-e[i]);
int sy = get(y);

if (d[sy] > D + 0) {
d[sy] = D;
q.push(PII(d[sy], y));
}
}
}
}
return;
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;
using namespace Graph;
init();

for (int i = 0; i < n; i++) scanf("%d", &p[i]);
while (m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z), add(y, x, z);
}

// query and dijkstra
int q;
cin >> q;
while (q--) {
scanf("%d%d%d", &C, &s, &t);
dijkstra();

if (res == inf) puts("impossible");
else printf("%d\n", res);
}
}