2025 道路修复 · 方案二预筛MST全局排序

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2341 字

原图缩成 n-1 树边后全局排序一次，每个子集只扫一遍

2025
最小生成树

正文

// CSP-S 2025 复赛 T2 · 道路修复（方案二：基础 MST 预筛 + 全局一次排序，满分）
// 原题：https://oj.yecheng.tv/p/2467
// 题意：同方案一（n, m ≤ 1e5、k ≤ 10，需满分口径）。
// 思路：
//   关键观察一：不改造乡镇时原图的边只有 MST 上的 n-1 条有用，
//   其余边在任何子集里都更差（乡镇星型边只会更优），先跑一遍
//   Kruskal 把原图缩成 n-1 条树边。
//   关键观察二：把树边与全部 k·n 条乡镇边放在一起全局排序一次，
//   枚举 2^k 个子集时只需按序扫一遍边表、跳过未选乡镇即可，
//   不必每个子集重新排序。
//   代价 = Σ_{j∈S} c[j] + 选中树边权和，取最小。
// 复杂度：O(m log m + 2^k · (n + kn) · α)，n = 1e5、k = 10 约 0.5s。
// 易错点：
//   1. 预筛后树边数恰 n-1，Kruskal 中 need = n + |S| - 1；
//   2. 乡镇节点编号用 n + j，跳边判 S 的对应位；
//   3. 全部费用 long long，输出可能到 1e13。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

struct E {
    int u, v;
    ll w;
    bool operator<(const E &o) const { return w < o.w; }
};

int fa[10015];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<E> edges(m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %lld", &edges[i].u, &edges[i].v, &edges[i].w);
        edges[i].u--; edges[i].v--;
    }
    sort(edges.begin(), edges.end());
    vector<E> base;
    for (int i = 0; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m && (int)base.size() < n - 1; i++) {
        int ru = find(edges[i].u), rv = find(edges[i].v);
        if (ru != rv) { fa[ru] = rv; base.push_back(edges[i]); }
    }
    vector<E> all(base);
    vector<ll> cost(k);
    for (int j = 0; j < k; j++) {
        scanf("%lld", &cost[j]);
        for (int i = 0; i < n; i++) {
            ll a;
            scanf("%lld", &a);
            all.push_back({n + j, i, a});
        }
    }
    sort(all.begin(), all.end());
    ll best = -1;
    for (int S = 0; S < (1 << k); S++) {
        ll c = 0;
        for (int j = 0; j < k; j++)
            if (S >> j & 1) c += cost[j];
        for (int i = 0; i < n + k; i++) fa[i] = i;
        int need = n + __builtin_popcount(S) - 1, got = 0;
        ll tot = c;
        for (auto &e : all) {
            if (e.u >= n && !(S >> (e.u - n) & 1)) continue;
            int ru = find(e.u), rv = find(e.v);
            if (ru != rv) {
                fa[ru] = rv;
                tot += e.w;
                if (++got == need) break;
            }
        }
        if (got == need && (best < 0 || tot < best)) best = tot;
    }
    printf("%lld\n", best);
    return 0;
}

2025 道路修复 · 方案二 预筛MST全局排序

正文

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

2025 道路修复 · 方案二预筛MST全局排序