这部分内容对最短路做一个补充
包括 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)=1⇔i,jd(i, j) = 1 \Leftrightarrow i, j 有关系
d(i,j)=0⇔i,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=1mAik⋅BkjC_{i j}=\sum_{k=1}^{m} A_{i k} \cdot B_{k j}

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

∀j∈[1,n], Fj′=∑k=1nFk⋅Akj\forall j \in [1, n], \ F^{\prime}_j = \sum_{k=1}^{n} F_k \cdot A_{kj}

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

Fibn+1=Fibn+Fibn−1 F(n)=(Fibn, Fibn+1)F(n−1)=(Fibn−1, 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}

(Fibn−1,Fibn)(0111)=(Fibn,Fibn+1)=(Fibn,Fibn−1+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(n−1)⋅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={an−1⋅an 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)2⋅7(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)=min⁡k∈[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)=min⁡k∈[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]);
        }
    }
}