最小 Steiner 树学习笔记

· · 题解

问题 给定带权无向连通图 G 和关键点集 P。选出包含 P 的边权和最小连通子图。

这个问题被称作最小 Steiner 树,可以证明是 NP-Hard 的。

性质 最优子图必然是树。

证明 若子图有环,任意删去环上一条边,边权和减小且仍然合法。

设 f_{u,S} 表示以 u 为根,包含 S 的最小 Steiner 树边权和,其中 S \subseteq P。记 u 的目的是钦定接口便于合并。转移分两步:

注意转移顺序是,外层按二进制序枚举 S,先枚举子集转移所有 u,再枚举 v 并松弛 u。

DP 初值 f_{u,\varnothing}=0,对 u \in P 令 f_{u,\{u\}}=0,其余 +\infty。答案为 \min \limits_{u} f_{u,P}。

容易 Floyd 做到 O(n3^k+n^22^k+n^3)。最优化 DP 在图上的转移顺序就是最短路,可以用多源 dij 优化第二步,做到 O(n3^k+m \log m 2^k)。

const int N = 1e5 + 5;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k; i64 f[35][N];
vector<pair<int, i64>> e[N];

struct node {
    int to; i64 dis;
    node(int v = 0, i64 w = 0) : to(v), dis(w) {}
    bool operator< (const node& o) const {return dis > o.dis;}
};
void dijkstra(i64* f) {
    priority_queue<node> Q;
    for (int i = 1; i <= n; i++)
        if (f[i] < inf) Q.emplace(i, f[i]);
    while (!Q.empty()) {
        auto [u, d] = Q.top(); Q.pop();
        if (d != f[u]) continue;
        for (auto [v, w] : e[u]) if (f[v] > f[u] + w)
            f[v] = f[u] + w, Q.emplace(v, f[v]);
    }
}

void _main() {
    cin >> n >> k >> m;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[0][i] = 0;
    for (int i = 1, x; i <= k; i++) 
        cin >> x, f[1<<(i-1)][x] = 0;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        e[u].pb(v, w), e[v].pb(u, w);
    }
    for (int s = 1; s < (1<<k); s++) {
        for (int u = 1; u <= n; u++) 
            for (int t = s; t; t = (t-1) & s) { 
                if ((s ^ t) > t) break;
                chkmin(f[s][u], f[t][u] + f[s ^ t][u]);
            }
        dijkstra(f[s]);
    }
    i64 res = inf;
    for (int u = 1; u <= n; u++) chkmin(res, f[(1<<k)-1][u]);
    cout << res;
}