思路与算法

先对原有道路求一棵MST，只保留n-1条原边；把所有乡镇到城市的候选边与这些树边合并排序。枚举改造乡镇的子集，先付改造费，再对原城与选中乡镇用Kruskal，跳过未选乡镇的边，取最小总费用。可用当前最优值剪掉已不可能更优的非负费用分支。

正确性说明

原图MST路径上每条边不重于任意连接该路径两端的被删原边。固定乡镇选择的任意扩展生成树中，若含原图非MST边e，删e形成割，原MST对应路径必有跨割边且权≤e，可替换；反复替换得到只用原MST原边的不劣方案。因此稀疏化不丢最优。固定子集后改造费固定，Kruskal安全边性质求所选全部顶点的最小连接费用；最优方案不会保留付费却无用的乡镇，枚举所有子集覆盖最优选择，含空子集。

复杂度

含边读入、排序、每个子集并查集初始化，O(m log m+(n+nk)log(n+nk)+2^k*(n+nk)*alpha(n+k))时间，O(m+nk+n+2^k)空间。

易错点

乡镇间没有直连道路，改造费只付一次。原边可有平行边与0费用，不能假定简单图；总费用使用64位。只要求原城连通，无用乡镇可不选。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
    void reset() {
        iota(p.begin(), p.end(), 0);
        fill(s.begin(), s.end(), 1);
    }
};
struct Edge {
    int u, v, w, owner;
};
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<Edge> original(m);
    for (auto &e : original) {
        cin >> e.u >> e.v >> e.w;
        e.u--;
        e.v--;
        e.owner = 0;
    }
    sort(original.begin(), original.end(), [](Edge a, Edge b) {
        return a.w < b.w;
    });
    DS d(n + k);
    vector<Edge> edges;
    edges.reserve(n - 1 + n * k);
    long long ans = 0;
    for (auto e : original)
        if (d.join(e.u, e.v)) {
            edges.push_back(e);
            ans += e.w;
        }
    vector<Edge>().swap(original);
    vector<long long> cost(k);
    for (int j = 0; j < k; j++) {
        cin >> cost[j];
        for (int i = 0; i < n; i++) {
            int w;
            cin >> w;
            edges.push_back({i, n + j, w, 1 << j});
        }
    }
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.w < b.w;
    });
    vector<long long> activation(1 << k);
    for (int mask = 1; mask < (1 << k); mask++) {
        int bit = __builtin_ctz((unsigned)mask);
        activation[mask] = activation[mask ^ (1 << bit)] + cost[bit];
    }
    for (int mask = 1; mask < (1 << k); mask++) {
        long long sum = activation[mask];
        if (sum >= ans)
            continue;
        d.reset();
        int need = n + __builtin_popcount((unsigned)mask) - 1, used = 0;
        for (auto e : edges)
            if (!e.owner || (mask & e.owner)) {
                if (d.join(e.u, e.v)) {
                    sum += e.w;
                    used++;
                    if (sum >= ans)
                        break;
                    if (used == need) {
                        ans = sum;
                        break;
                    }
                }
            }
    }
    cout << ans << "\n";
}