矩阵乘法与路径问题

矩阵乘法与图论结合，可以解决以下问题

• 任意两点间只经过 \(n\) 条边的总路径的数量
• 任意两点间经过 \(n\) 条边的最短路径长度

下面我们只讲结论，证明可用数学归纳法。

两点间只经过 \(n\) 条边的总路径的数量

用邻接矩阵M表示一个图，\(M(i, j)\) 为其第 \(i\) 行第 \(j\) 列元素，表示 \(i\) 和 \(j\) 的直连关系
若 \(i\) 与 \(j\) 直接连接，则 \(M(i, j) = 1\)，否则 \(M(i, j) = 0\)
特别的，当 \(i=j\) 时，\(M(i, j) = 0\)

计算邻接矩阵 \(M\) 的幂 \(G = M^n\)，其元素 \(G(i, j)\) 的值是从 \(i\) 点到 \(j\) 点经过 \(n\) 条边（或 \(n-1\) 和点）的总路径数量

两点间经过 \(n\) 条边的最短路径长度

首先对邻接矩阵以及矩阵乘法做一下推广

用邻接矩阵 \(M\) 表示一个图，\(M(i, j)\) 为其第 \(i\) 行第 \(j\) 列元素，表示 \(i\) 和 \(j\) 的直连关系
若 \(i\) 与 \(j\) 直连，则 \(M(i, j) = w_{i, j}\)，其中 \(w_{i, j}\) 表示边 \(ij\) 的权值。否则 \(M(i, j) = \infty\)
特别的，当 \(i=j\) 时，\(M(i, j) = \infty\)

定义广义的矩阵乘法 \(M \times M = \min^{N}_{a=1} [M(i, a)+M(a, j)]\)

计算邻接矩阵 \(M\) 的广义幂 \(G = M^n\)，其元素 \(G(i, j)\) 的值是从 \(i\) 点到 \(j\) 点经过 \(n\) 条边（或 \(n-1\) 和点）的最短路径长度

求解本题

时间复杂度分析

矩阵乘法 \(O(N^3)\)，这样的乘法需要进行 \(n\) 次，故总复杂度为 \(O(N^3 \times n)\)
本题中 \(N < 200, n \leqslant 10^6\)，直接计算会超时。
使用矩阵快速幂优化，复杂度降为 \(O(N^3 \times log_2 n)\)

注意本题还需要离散化。

AC Code

#include<bits/stdc++.h>
using namespace std;

int n, t, s, e;
int hsh[1005], cnt;

struct matrix{
    int mat[125][125];
    
    matrix operator * (const matrix& other) const{
        matrix ans;
        memset(ans.mat, 0x3f, sizeof ans.mat);
        for(int i=1; i <= cnt; i++){
            for(int j=1; j <= cnt; j++){
                for(int k=1; k<=cnt; k++){
                    ans.mat[i][j] = min(ans.mat[i][j], mat[i][k] + other.mat[k][j]);
                }
            }
        }
        return ans;
    }
    
    matrix& operator=(const matrix& other) {
        if (this != &other) {
            memcpy(mat, other.mat, sizeof(mat)); // 深拷贝矩阵内容
        }
        return *this;
    }
    
    matrix pow(int n){
        matrix ans, tmp;
        ans = *this;
        tmp = *this;
        n--;
        while(n) {
            if (n & 1) ans = ans*tmp;
            tmp = tmp * tmp;
            n >>= 1;
        }
        return ans;
    }
}mat;

int main(){
    cin>>n>>t>>s>>e;
    memset(mat.mat, 0x3f, sizeof mat.mat);
    for(int i=0, w,u,v; i<t; i++){
        cin>>w>>u>>v;
        if (!hsh[u]) hsh[u] = ++cnt;
        if (!hsh[v]) hsh[v] = ++cnt;
        mat.mat[hsh[u]][hsh[v]] = mat.mat[hsh[v]][hsh[u]] = w;
    }
    
    matrix ans = mat.pow(n);
    cout<<ans.mat[hsh[s]][hsh[e]]<<endl;
    
    return 0;
}

下面是官方题解

USACO NOV07 Problem 'relays' Analysis

by Neal Wu

First, note that there cannot be more than T distinct nodes in our graph, because there are exactly T edges in the graph, and each node is an endpoint for at least two edges.

The simplest solution that is reasonably fast is to let s[L][V] be the shortest path from node S to node V that has length L. We can compute the values in this array by iterating N times, each time trying to travel through one edge from each node. The memory for this can be reduced by using a sliding window (since computing the values for length L only uses the values for length L - 1), and this solution uses O(N T²) time. To obtain a faster solution, we do the following.

Assume we have the shortest path, from S to E, of length N. Then we can break up this path into smaller paths whose lengths are powers of two. Thus, we can compute, for each power of two that is no greater than N, the shortest path between every pair of nodes that has a length of that power of two. This can be done using a method similar to Floyd-Warshall in O(T³ log N) time. (See the code below for more details.)

After we compute the shortest paths mentioned above, we can compute shortest paths, of length N, from S to every other node. We do this by breaking N up into its binary representation, and for each power of two that occurs, we compute shortest paths after adding in paths of length equal to this power. This can be done in O(T² log N) time. (Again, see the code below for more details.) Thus, our overall runtime is O(T³ log N).

#include <cstdio>
#include <cstring>
using namespace std;

FILE *fout = fopen ("relays.out", "w");
FILE *fin = fopen ("relays.in", "r");

const int INF = 1000000000;
const int MAXV = 105;
const int MAXI = 1005;
const int MAXL = 20;

int N, V, T, S, E;

// compress nodes to smaller values
int change [MAXI];

// shortest path between two nodes with a length of a power of two
int dist [MAXL][MAXV][MAXV];

// best path from S to a node
int best [MAXV], best2 [MAXV];

// change a node to a 'compressed' value
inline void check (int &ind)
{
    if (change [ind] == -1)
        change [ind] = V++;

    ind = change [ind];
}
 
int main () {
// initialize arrays
    memset (change, -1, sizeof (change));
    memset (dist, 63, sizeof (dist));
    memset (best, 63, sizeof (best));

    fscanf (fin, "%d %d %d %d", &N, &T, &S, &E);

    check (S);
    check (E);

    for (int i = 0; i < T; i++) {
        int A, B, L;

        fscanf (fin, "%d %d %d", &L, &A, &B);

        check (A);
        check (B);

// edges are paths of length 1
        dist [0][A][B] <?= L;
        dist [0][B][A] <?= L;
    }

// compute shortest paths whose lengths are powers of two
// a path of length 2^p can be made by two paths of length 2^(p - 1)
    for (int p = 1; (1 << p) <= N; p++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist [p - 1][i][j] < INF)
                    for (int k = 0; k < V; k++)
                        if (dist [p - 1][i][j] + dist [p - 1][j][k] < dist [p][i][k])
                            dist [p][i][k] = dist [p - 1][i][j] + dist [p - 1][j][k];


// combine results of each power of two in the binary representation of N
    best [S] = 0;

    for (int p = 0; (1 << p) <= N; p++)
        if (N & (1 << p)) {
// use a temporary array 'best2' to hold the new values, and copy them to the old array afterward
            memset (best2, 63, sizeof (best2));

            for (int i = 0; i < V; i++)
                if (best [i] < INF)
                    for (int j = 0; j < V; j++)
                        if (best [i] + dist [p][i][j] < best2 [j])
                            best2 [j] = best [i] + dist [p][i][j];

            memcpy (best, best2, sizeof (best2));
        }

// best [E] is now the shortest path from S to E using N edges
    fprintf (fout, "%d\n", best [E]);

    return 0;
}