2022 数据传输 · 方案二倍增加矩阵

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3952 字
k 步转移压成 min-plus 矩阵，倍增逐位合并
2022
树
正文

// CSP-S 2022 复赛 T4 · 数据传输（方案二：倍增 + min-plus 矩阵，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2022D
// 题意：同方案一（k ≤ 3，n, Q ≤ 2e5，需满分）。
// 思路（k 步转移的 min-plus 矩阵 + 倍增合并）：
//   路径 s→t 上依次经过 p0=s, p1, ..., pt=t。转移约束：相邻停留点
//   的树上距离 ≤ k。把"在点 x 停留"的费用 w_x 只在"到达该点"时计。
//   定义矩阵乘法为 (min, +)：M[i][j] = 从"距 u 还剩 i 类状态"到
//   "剩余 j"的最小代价。经典建模：
//   对每条边 (u, v)，转移矩阵 E(k×k)：跨过这条边的状态推进。
//   实现（主流写法）：
//   - 状态 i = "还要走 ≥ i 步才允许停"（i = 0..k-1）；
//   - 预处理 up[j][u]：u 向上 2^j 步的合成矩阵，以及祖先数组；
//   - 询问：把 s→t 的路径拆成 s→lca 与 lca→t 两段，各用二进制
//     拆分合成矩阵，最后合并两段 + 端点权。
//   矩阵大小 k ≤ 3 → 3×3，合并 O(k^3)，单询问 O(k^3 log n)。
//   本卡给出完整骨架（矩阵定义 + 倍增 + 询问合并）。
// 复杂度：O((n + q) · k^3 · log n)。
// 易错点：
//   1. 端点权只计一次：起点算入初始状态，终点在合并后补上；
//   2. min-plus 的单位元是 0 矩阵的对角 0、其余 INF；
//   3. 上行与下行的矩阵方向不同（转置）；
//   4. INF 用 long long 上限的一半防加法溢出。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const long long INF = 4e18;
int n, q, k;
long long w[200005];
vector<int> g[200005];
int dep[200005], up[18][200005];

struct Mat {
    long long a[3][3];
};

Mat mul(const Mat& x, const Mat& y) {
    Mat z;
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++) {
            z.a[i][j] = INF;
            for (int t = 0; t < k; t++)
                if (x.a[i][t] < INF && y.a[t][j] < INF)
                    z.a[i][j] = min(z.a[i][j], x.a[i][t] + y.a[t][j]);
        }
    return z;
}

Mat edgeMat(int from, int to) {
    // 从 from 走到 to（一步）：状态推进矩阵
    // 状态 i 表示"进入 to 前已连续移动 i+1 步内可停"（k≤3，简化口径：
    // 矩阵 [i][j] = 从状态 i 经此边到状态 j 的最小费用）
    Mat m;
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++) m.a[i][j] = INF;
    // 走一步：任何状态都可"停"（j=0，付 w[to]）或继续走（j=i+1 < k）
    for (int i = 0; i < k; i++) {
        m.a[i][0] = w[to];               // 在 to 停下（计费）
        if (i + 1 < k) m.a[i][i + 1] = 0; // 继续滑行（未停，不计费）
    }
    (void)from;
    return m;
}

Mat upMat[18][200005];

void dfs(int u, int fa) {
    up[0][u] = fa;
    dep[u] = dep[fa] + 1;
    if (fa) upMat[0][u] = edgeMat(u, fa);
    for (int v : g[u])
        if (v != fa) dfs(v, u);
}

int main() {
    freopen("transmit.in", "r", stdin);
    freopen("transmit.out", "w", stdout);
    scanf("%d%d%d", &n, &q, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dep[0] = 0;
    dfs(1, 0);
    for (int j = 1; j < 18; j++)
        for (int u = 1; u <= n; u++) {
            up[j][u] = up[j - 1][up[j - 1][u]];
            if (up[j][u]) upMat[j][u] = mul(upMat[j - 1][u], upMat[j - 1][up[j - 1][u]]);
        }
    while (q--) {
        int s, t;
        scanf("%d%d%d", &s, &t, &k);
        // 收集路径矩阵：s 上行到 lca，t 上行到 lca，再合成
        // （完整实现：二进制拆分 + 首尾状态拼合；骨架如下）
        int a = s, b = t;
        if (dep[a] < dep[b]) swap(a, b);
        Mat left, right;
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++) {
                left.a[i][j] = (i == 0 && j == 0) ? w[s] : INF;
                right.a[i][j] = (i == 0 && j == 0) ? 0 : INF;
            }
        int diff = dep[a] - dep[b];
        for (int j = 0; j < 18 && a != b; j++)
            if (diff >> j & 1) {
                left = mul(left, upMat[j][a]);
                a = up[j][a];
            }
        if (a != b) {
            for (int j = 17; j >= 0; j--)
                if (up[j][a] != up[j][b]) {
                    left = mul(left, upMat[j][a]);
                    right = mul(upMat[j][b], right);
                    a = up[j][a];
                    b = up[j][b];
                }
            left = mul(left, edgeMat(a, up[0][a]));
            right = mul(edgeMat(b, up[0][a]), right);
            a = up[0][a];
        }
        Mat res = mul(left, right);
        long long ans = INF;
        for (int i = 0; i < k; i++)
            ans = min(ans, res.a[0][i] + w[t]);
        printf("%lld\n", ans);
    }
    return 0;
}
2022 数据传输 · 方案二 倍增加矩阵

正文

CSP-S 标程 · 复赛真题的其它内容

2022 数据传输 · 方案二倍增加矩阵
