道路修复(Road Repair) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v;
    long long w;
    int tag; // -1 for base tree edge, 0..k-1 for town j
    bool operator<(const Edge& o) const { return w < o.w; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    vector<Edge> raw(m);
    for (int i = 0; i < m; ++i) {
        cin >> raw[i].u >> raw[i].v >> raw[i].w;
        raw[i].tag = -1;
    }
    sort(raw.begin(), raw.end());
    vector<int> p(n + k + 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    };
    vector<Edge> cand;
    cand.reserve(n * (k + 1));
    long long baseAns = 0;
    for (const auto& e : raw) {
        int ru = find(e.u), rv = find(e.v);
        if (ru != rv) {
            p[ru] = rv;
            baseAns += e.w;
            cand.push_back(e);
        }
    }
    vector<long long> c(k);
    for (int j = 0; j < k; ++j) {
        cin >> c[j];
        for (int i = 1; i <= n; ++i) {
            long long w;
            cin >> w;
            cand.push_back({n + 1 + j, i, w, j});
        }
    }
    sort(cand.begin(), cand.end());
    long long ans = baseAns;
    int totMask = 1 << k;
    for (int mask = 1; mask < totMask; ++mask) {
        long long cur = 0;
        int needNodes = n;
        for (int j = 0; j < k; ++j) {
            if ((mask >> j) & 1) {
                cur += c[j];
                ++needNodes;
            }
        }
        if (cur >= ans) continue;
        iota(p.begin(), p.end(), 0);
        int cnt = 0;
        for (const auto& e : cand) {
            if (e.tag != -1 && !((mask >> e.tag) & 1)) continue;
            int ru = find(e.u), rv = find(e.v);
            if (ru != rv) {
                p[ru] = rv;
                cur += e.w;
                if (cur >= ans) break;
                if (++cnt == needNodes - 1) break;
            }
        }
        if (cnt == needNodes - 1 && cur < ans) ans = cur;
    }
    cout << ans << "\n";
    return 0;
}