洛谷 P2886. Cow Relays G

问题描述

link

分析

题目要求：给定一张 $T$ 条边的无向连通图（顶点编号不超过 $1000$），求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边的最短路长度。其中 $N$ 可以很大（$N\le {10}^6$），所以路径允许（也往往必须）重复经过顶点和边。

关键点有两个：

1. 离散化：虽然顶点编号最大到 $1000$，但真正会走到的只有边的端点和 $S$、$E$，最多 $2T+2\le 202$ 个。先把它们排序去重、映射到 $1\dots p$，矩阵的规模就从 $1000$ 降到了 $p\le 202$，这是后面矩阵快速幂可行的前提。
2. "恰好 $N$ 条边"不能用普通最短路：Dijkstra/Floyd 求的是"任意条边"的最短路，无法控制恰好 $N$ 条；且 $N$ 很大时路径必然绕圈走重复边，必须用能刻画"边数"的状态转移。

思路一：滚动数组 DP

设 $f[i][j]$ 表示从 $S$ 出发、恰好经过 $i$ 条边到达 $j$ 的最短路长度。转移枚举到达 $j$ 的最后一条边 $(u,j)$：

$f[i][j]=\underset{(u,j)\in E}{min}(f[i-1][u]+w(u,j))$

初始 $f[0][S]=0$，其余为 $+\mathrm{\infty }$；转移只依赖 $i-1$ 层，所以用两行滚动数组即可，空间 $O(p)$。逐层递推 $N$ 次，每次对所有顶点枚举其邻边，总复杂度 $O(N\cdot T)$。本题 $N\le {10}^6$、$T\le 100$，洛谷数据下可以通过（在 AcWing 上会超时，见文首注释）。

思路二：矩阵快速幂（Min-Plus 代数）

把"恰好经过 $i$ 条边"看成广义矩阵乘法。定义 $d[i][j]$ 为从 $i$ 到 $j$ 恰好经过 1 条边的最短长度（无直达边为 $+\mathrm{\infty }$，重边取最小值）。对两个矩阵定义广义乘法：

$C[i][j]=\underset{1\le k\le p}{min}(A[i][k]+B[k][j])$

若 $A$ 表示"恰好 $a$ 条边"的最短路矩阵、$B$ 表示"恰好 $b$ 条边"的，则 $A\otimes B$ 表示先走 $a$ 条边、再走 $b$ 条边的拼接，恰好是"$a+b$ 条边"的最短路矩阵。这个运算是结合的（路径拼接天然满足结合律），所以可以用二进制快速幂计算 $d^N$，答案就是 $d^N[S][E]$。

初始矩阵 $ans$ 是"恰好 0 条边"的单位元：$ans[i][i]=0$，其余为 $+\mathrm{\infty }$。快速幂过程：

• 若 $N$ 的当前最低位为 $1$，执行 $ans=ans\otimes d$；
• 每次循环后 $d=d\otimes d$，$N$ 右移一位。

复杂度：每次广义矩阵乘法 $O(p^3)$，共 $O(\log N)$ 次，总复杂度 $O(p^3\log N)$（$p\le 202$，约 $1.6\times {10}^8$ 量级，可过）。

正确性：任意一条恰好 $N$ 条边的路径都可以拆成若干段拼接，广义矩阵幂按二进制分解逐段合并，等价于枚举所有"恰好 $N$ 条边"的路径并取最小值；无向图保证矩阵对称，且题目保证 $S$、$E$ 连通、答案存在。

参考代码

此代码在AcWing上会超时！洛谷可过！

$O(NT)$

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

int h[210], e[210], ne[210], w[210], tot;
// f[i][j] 表示从 st 出发到达 j 恰好经过 i 条边的最短路
int f[2][210];
int v[210], a[110], b[110], c[110];
int n, t, st, ed, m, p;

void add(int a, int b, int c) {
    e[++tot] = b;
    w[tot] = c;
    ne[tot] = h[a];
    h[a] = tot;
}

int main() {
    cin >> n >> t >> st >> ed;
    v[++m] = st;
    v[++m] = ed;

    for (int i = 1; i <= t; i++) {
        cin >> c[i] >> a[i] >> b[i];
        v[++m] = a[i];
        v[++m] = b[i];
    }
    sort(v + 1, v + 1 + m);
    p = unique(v + 1, v + 1 + m) - (v + 1);
    st = lower_bound(v + 1, v + 1 + p, st) - v;
    ed = lower_bound(v + 1, v + 1 + p, ed) - v;

    for (int i = 1; i <= t; i++) {
        a[i] = lower_bound(v + 1, v + 1 + p, a[i]) - v;
        b[i] = lower_bound(v + 1, v + 1 + p, b[i]) - v;
        add(a[i], b[i], c[i]);
        add(b[i], a[i], c[i]);
    }

    memset(f, 0x3f, sizeof f);
    f[0][st] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= p; j++) {
            f[i & 1][j] = 0x3f3f3f3f;
            for (int k = h[j]; k; k = ne[k]) {
                f[i & 1][j] = min(f[i & 1][j], f[i - 1 & 1][e[k]] + w[k]);
            }
        }
    }
    cout << f[n & 1][ed] << endl;

    return 0;
}

$O(T^3\log N)$

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

int v[210], a[110], b[110], c[110];
int d[210][210], ans[210][210];
int n, t, st, ed, m, p;

void mul(int a[][210], int b[][210]) {
    int c[210][210];
    memset(c, 0x3f, sizeof c);

    for (int i = 1; i <= p; i++) {
        for (int j = 1; j <= p; j++) {
            for (int k = 1; k <= p; k++) {
                c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
            }
        }
    }

    memcpy(a, c, sizeof c);
}

int main() {
    cin >> n >> t >> st >> ed;
    v[++m] = st;
    v[++m] = ed;

    for (int i = 1; i <= t; i++) {
        cin >> c[i] >> a[i] >> b[i];
        v[++m] = a[i];
        v[++m] = b[i];
    }
    sort(v + 1, v + 1 + m);
    p = unique(v + 1, v + 1 + m) - (v + 1);
    st = lower_bound(v + 1, v + 1 + p, st) - v;
    ed = lower_bound(v + 1, v + 1 + p, ed) - v;

    memset(d, 0x3f, sizeof d); // 经过 1 条边的最短路
    for (int i = 1; i <= t; i++) {
        a[i] = lower_bound(v + 1, v + 1 + p, a[i]) - v;
        b[i] = lower_bound(v + 1, v + 1 + p, b[i]) - v;
        d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]);
        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i]);
    }

    memset(ans, 0x3f, sizeof ans);
    ans[st][st] = 0;

    while (n) {
        if (n & 1) mul(ans, d);
        mul(d, d);
        n >>= 1;
    }

    cout << ans[st][ed] << endl;

    return 0;
}