2025 道路修复 · 方案一逐子集重建MST

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

枚举 2^k 改造子集，全边表重排序跑 Kruskal

2025
最小生成树

正文

// CSP-S 2025 复赛 T2 · 道路修复（方案一：全边表逐子集 Kruskal）
// 原题：https://oj.yecheng.tv/p/2467
// 题意：n 座城市 m 条无向路，另有 k 个乡镇，乡镇 j 与每城 i 之间
// 可修一条权 a[j][i] 的路，但启用乡镇 j 需一次性缴费 c[j]。
// 求让全图连通的最小总花费：可以改造任意乡镇子集 S，
// 花费 = Σ_{j∈S} c[j] + 生成树边权之和。
// （本题在 OJ 上为标准输入输出，无需文件重定向。）
// 思路：
//   枚举 2^k 个改造子集 S，把基础 m 条边与 S 中乡镇的全部 n 条
//   星型边一起排序做 Kruskal，生成树需要 n + |S| - 1 条边；
//   总代价 = Σ c[j] + 树边权和，取所有子集的最小值。
// 复杂度：O(2^k · (m + kn) log(m + kn))，小数据可过；满分见方案二。
// 易错点：
//   1. 未选乡镇的边必须整段跳过，不能只跳部分；
//   2. 生成树边数是 n + |S| - 1，不是 n - 1；
//   3. 边权和可达 1e13，用 long long。
#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[105];
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> base(m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %lld", &base[i].u, &base[i].v, &base[i].w);
        base[i].u--; base[i].v--;
    }
    vector<ll> cost(k);
    vector<vector<ll>> a(k, vector<ll>(n));
    for (int j = 0; j < k; j++) {
        scanf("%lld", &cost[j]);
        for (int i = 0; i < n; i++) scanf("%lld", &a[j][i]);
    }
    ll best = -1;
    for (int S = 0; S < (1 << k); S++) {
        vector<E> all(base);
        ll c = 0;
        for (int j = 0; j < k; j++)
            if (S >> j & 1) {
                c += cost[j];
                for (int i = 0; i < n; i++) all.push_back({n + j, i, a[j][i]});
            }
        sort(all.begin(), all.end());
        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; got++; }
        }
        if (got == need && (best < 0 || tot < best)) best = tot;
    }
    printf("%lld\n", best);
    return 0;
}

2025 道路修复 · 方案一 逐子集重建MST

正文

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

2025 道路修复 · 方案一逐子集重建MST