这部分内容对最短路做一个补充
包括floydfloyd 算法和传递闭包

floyd 算法

floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dist[maxn][maxn];

void initG() {
Set(dist, inf);
_rep(i, 1, N) dist[i][i] = 0;
}

void floyd() {
_rep(k, 1, N) {
_rep(i, 1, N) _rep(j, 1, N) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}

int main() {
initG();
_rep(i, 1, m) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
d[x][y] = min(d[x][y], z);
}
floyd();
}

二元关系传递闭包
d(i,j)d(i, j)0,10, 1 矩阵, 表示二元关系
d(i,j)=1i,jd(i, j) = 1 \Leftrightarrow i, j 有关系
d(i,j)=0i,jd(i, j) = 0 \Leftrightarrow i, j 没有关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool d[maxn][maxn];

void initG() {
Set(d, 0);
}

void floyd() {
_rep(k, 1, n) {
_rep(i, 1, n) _rep(j, 1, n) {
d[i][j] |= (d[i][k] & d[k][j]);
}
}
}

int main() {
_rep(i, 1, n) d[i][i] = 1;
_rep(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
d[x][y] = d[y][x] = 1;
}
floyd();
}

有向图传递闭包

d(i,j)=1d(i,j)=1 表示(i,j)(i, j) 之间有约束关系
关系的传递性可以用有向图传递闭包的方式来解决

POJ1094

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
const int maxn = 30;
int f[maxn][maxn], G[maxn][maxn];
int deg[maxn];
int n, m;
char str[5];

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

// == floyd algorithm ==
void floyd() {
_for(k, 0, n) _for(i, 0, n) _for(j, 0, n) {
f[i][j] |= (f[i][k] & f[k][j]);
}
}
// == floyd finsihed ==

// == topo sort ==
void topo(const int t) {
queue<int> que;
_for(i, 0, n) if(deg[i] == 0) que.push(i);
printf("Sorted sequence determined after %d relations: ", t);

while (!que.empty()) {
int x = que.front(); que.pop();
printf("%c", (char)('A' + x));
_for(y, 0, n) {
if(G[x][y]) if(--deg[y] == 0) que.push(y);
}
}
printf(".\n");
}
// == topo finsihed ==

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

bool found = false, fail = false;
int t = 0;
_rep(i, 1, m) {
scanf("%s", str);
if(found || fail) continue;

int u = str[0] - 'A';
int v = str[2] - 'A';
G[u][v] = f[u][v] = 1;
deg[v]++;
floyd();

found = true;
_for(u, 0, n) {
if(f[u][u]) {
fail = true;
break;
}
_for(v, 0, n) {
if(v != u && (f[u][v] ^ f[v][u]) == 0) found = false;
}
}
t = i;
}
if(fail) printf("Inconsistency found after %d relations.\n", t);
else if(found) topo(t);
else printf("Sorted sequence cannot be determined.\n");
}
}

无向图最小环

POJ1734
POJ1734

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
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

// == Graph definition ==
int c[maxn][maxn], d[maxn][maxn];
int pos[maxn][maxn];
int ans = inf;

vector<int> path;

void init() {
Set(c, inf);
_rep(i, 1, n) c[i][i] = 0;
Set(pos, 0);
ans = inf;

path.clear();
}
// == Graph finished ==

// == floyd algorithm ==
void initFloyd() {
Cpy(d, c);
}

inline void getPath(int x, int y, vector<int>& path) {
if(pos[x][y] == 0) return;
getPath(x, pos[x][y], path);
path.push_back(pos[x][y]);
getPath(pos[x][y], y, path);

}

void floyd() {
initFloyd();
_rep(k, 1, n) {
_for(i, 1, k) _for(j, i + 1, k) {
if((ll)d[i][j] + c[j][k] + c[k][i] < ans) {
ans = d[i][j] + c[j][k] + c[k][i];
//debug(ans);

path.clear();
path.push_back(i);
getPath(i, j, path);
path.push_back(j);
path.push_back(k);
}
}
_rep(i, 1, n) _rep(j, 1, n) {
if(d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;
}
}
}
}
// == floyd finsihed ==

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

// build graph
init();
_rep(i, 1, m) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
c[x][y] = c[y][x] = min(c[x][y], z);
}

// floyd
floyd();

if(ans == inf) {
puts("No solution."); return 0;
}
_for(i, 0, path.size()) printf("%d ", path[i]);
printf("\n");
}

矩阵乘法在最短路问题上的应用

矩阵乘法的定义

Cij=k=1mAikBkjC_{i j}=\sum_{k=1}^{m} A_{i k} \cdot B_{k j}

特殊情形,F(1×n),A(n×n)F(1×n)=FAF(1\times n), A(n \times n) \Rightarrow F^{\prime}(1\times n) = F \cdot A
省略FF 的第一维

j[1,n], Fj=k=1nFkAkj\forall j \in [1, n], \ F^{\prime}_j = \sum_{k=1}^{n} F_k \cdot A_{kj}

Fibonacci\text{Fibonacci}数列的矩阵形式

Fibn+1=Fibn+Fibn1 F(n)=(Fibn, Fibn+1)F(n1)=(Fibn1, Fibn)\begin{gathered} Fib_{n+1} = Fib_{n} + Fib_{n-1} \\ \ \\ F(n) = (Fib_{n}, \ Fib_{n+1}) \\ F(n-1) = (Fib_{n-1}, \ Fib_{n}) \end{gathered}

(Fibn1,Fibn)(0111)=(Fibn,Fibn+1)=(Fibn,Fibn1+Fibn)\begin{gathered} \left(Fib_{n-1}, Fib_{n} \right)\left(\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\right)=\left(Fib_{n}, Fib_{n+1}\right) =\left(Fib_{n}, Fib_{n-1}+Fib_{n}\right) \end{gathered}

F(n)=F(n1)A1==F(0)An F(0)={0,1}\begin{gathered} F(n) = F(n-1)\cdot A^1 = \cdots = F(0)\cdot A^n \\ \ \\ F(0) = \{0, 1\} \end{gathered}

快速幂计算

an={an1an is odd an/2n is even 1n=0\begin{gathered} a^{n}=\left\{\begin{array}{cc} a^{n-1} \cdot a & n \text { is odd } \\ a^{n / 2} & n \text { is even } \\ 1 & n=0 \end{array}\right. \end{gathered}

非递归的方法计算快速幂
比如需要计算7(1010)27^{(1010)_2}, 可以做拆分
7(1000)27(10)27^{(1000)_2} \cdot 7^{(10)_2}

对于ana^n

1
2
如果有 a & 1 == 1, 那么这一位就要计入,  ans *= a
如果有 a & 1 == 0, 那么只要把 a *= a , 不断底数平方就可以

7(100)2=71,72,74,7^{(100\cdots)_2} = 7^1, 7^2, 7^4, \cdots

1
2
3
4
5
6
7
8
int qpow(int a, int n) {
int ans = 1;
for(; n; n >>= 1) {
if(n & 1) ans *= a;
a *= a;
}
return ans;
}

Fibonacci计算

POJ3070

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
const int mod = 10000;
int n;
const int K = 2;

void mul(int f[K], int A[K][K]) {
int c[K];
Set(c, 0);

_for(j, 0, K) _for(k, 0, K) {
c[j] = (c[j] + (ll)f[k] * A[k][j]) % mod;
}
Cpy(f, c);
}

void mulself(int A[K][K]) {
int c[K][K];
Set(c, 0);
_for(i, 0, K) _for(j, 0, K) _for(k, 0, K) {
c[i][j] = (c[i][j] + (ll)(A[i][k]) * A[k][j]) % mod;
}
Cpy(A, c);
}

int main() {
freopen("input.txt", "r", stdin);
while (cin >> n && n != -1) {
int f[2] = {0, 1};
int A[2][2] = {{0, 1}, {1, 1}};

for(; n; n >>= 1) {
if(n & 1) mul(f, A);
mulself(A);
}
cout << f[0] << endl;
}
}

状态转移矩阵的构建

Acwing206

Acwing206

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
const int maxn = 10 + 5;
const int inf = 0x3f3f3f3f;
int n, m, t, act, N;

// == board definition ==
char str[maxn], op[maxn][maxn];
int bd[maxn][maxn], ptr[maxn][maxn];
// == board definition finished ==

// == get hash ==
inline int _hash(int i, int j) {
return (i - 1) * m + j;
}

vector<vector<ll> > A[60 + 5];
vector<vector<ll> > F;

void initHash() {
N = n * m + 1;
_rep(i, 1, 60) A[i].resize(N, vector<ll>(N));
F.resize(1, vector<ll>(N));
F[0][0] = 1;
_rep(i, 1, 60) A[i][0][0] = 1;
}
// == hash finished ==

// == build matrix ==
void build() {
_rep(k, 1, 60) {
_rep(i, 1, n) _rep(j, 1, m) {
int x = bd[i][j], y = ptr[i][j];

if(isdigit(op[x][y])) {
A[k][0][_hash(i, j)] = op[x][y] - '0';
A[k][_hash(i, j)][_hash(i, j)] = 1;
}
else if(op[x][y] == 'N' && i > 1) A[k][_hash(i, j)][_hash(i-1, j)] = 1;
else if(op[x][y] == 'S' && i < n) A[k][_hash(i, j)][_hash(i+1, j)] = 1;
else if(op[x][y] == 'W' && j > 1) A[k][_hash(i, j)][_hash(i, j-1)] = 1;
else if(op[x][y] == 'E' && j < m) A[k][_hash(i, j)][_hash(i, j+1)] = 1;

ptr[i][j] = (ptr[i][j] + 1) % strlen(op[x]);
}
}
}
// == build matrix finished ==

// == calculate ==
inline void mul(vector<vector<ll> > &A, const vector<vector<ll> > &B) {
vector<vector<ll> > ans;
ans.resize(A.size(), vector<ll>(B[0].size()));

_for(i, 0, A.size()) _for(j, 0, B[0].size()) {
_for(k, 0, B.size()) ans[i][j] = ans[i][j] + A[i][k] * B[k][j];
}

A = ans;
}

void solve() {
vector<vector<ll> > C = A[1];
_rep(i, 2, 60) mul(C, A[i]);

ll ans = 0;
int q = t / 60;
for(; q; q >>= 1) {
if(q & 1) mul(F, C);
mul(C, C);
}

int r = t % 60;
_rep(i, 1, r) mul(F, A[i]);

_for(i, 0, N) ans = max(ans, F[0][i]);
cout << ans << endl;
}
// == calculate finsihed ==

void init() {
Set(ptr, 0);
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m >> t >> act;

init();
// get input board
_rep(i, 1, n) {
scanf("%s", str + 1);
_rep(j, 1, m) bd[i][j] = str[j] - '0';
}
// get command
_for(i, 0, act) scanf("%s", op[i]);

// == input finished ==

// init Hash and build matrix
initHash();
build();

// calculate
solve();
}

floyd和矩阵乘法

POJ3613

POJ3613

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
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
int n, t, s, e, tot = 0;

map<int, int> mp;

// == status definition ==
struct Mat {
int A[maxn][maxn];

void _init() {
_for(i, 1, maxn) _for(j, 1, maxn) {
A[i][j] = inf;
}
}
} st, ed;
// == status finished ==

inline Mat mul(Mat a, Mat b) {
Mat c;
c._init();
_rep(i, 1, tot) _rep(j, 1, tot) _rep(k, 1, tot) {
c.A[i][j] = min(c.A[i][j], a.A[i][k] + b.A[k][j]);
}
return c;
}

void init() {
tot = 0;
mp.clear();
st._init();
ed._init();
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> t >> s >> e;
init();

// build Graph
while (t--) {
int x, y, z;
scanf("%d%d%d", &z, &x, &y);
x = mp[x] ? mp[x] : (mp[x] = ++tot);
y = mp[y] ? mp[y] : (mp[y] = ++tot);
st.A[x][y] = st.A[y][x] = z;
}
Cpy(ed.A, st.A);

// Matrix change
n--;
for(; n; n >>= 1) {
if(n & 1) ed = mul(ed, st);
st = mul(st, st);
}

cout << ed.A[mp[s]][mp[e]] << endl;
}

群运算观点下的floyd方程

d(i,j)=mink[1,n](d(i,j),d(i,k)+d(k,j))d(i, j) = \min_{k \in [1, n]}(d(i, j), d(i, k)+d(k, j))

其实可以做进一步的扩展, 因为加法运算有群封闭性和结合律
同样,min, max\min, \ \max 运算也具有结合律

那么诸如路径最大值尽可能小的问题, 也可以写出 floyd 方程

d(i,j)=mink[1,n]{d(i,j),max{d(i,k),d(k,j)}}d(i, j) = \min_{k \in [1, n]} \{d(i, j), \max\{d(i, k), d(k, j)\}\}

UVA10048

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
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;

int n, m, q;
int d[maxn][maxn];

void init() {
Set(d, 0);
_rep(i, 1, n) _rep(j, 1, n) d[i][j] = inf;
_rep(i, 1, n) d[i][i] = 0;
}

void floyd() {
_rep(k, 1, n) _rep(i, 1, n) _rep(j, 1, n) {
if(d[i][k] < inf && d[k][j] < inf) {
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
}
}
}

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

while (m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);

d[x][y] = d[y][x] = min(d[x][y], z);
}

// run floyd()
floyd();

if(kase > 0) printf("\n");
printf("Case #%d\n", ++kase);

// query
while (q--) {
int q1, q2;
scanf("%d%d", &q1, &q2);
if(d[q1][q2] == inf) printf("no path\n");
else printf("%d\n", d[q1][q2]);
}
}
}