#acm #图论

最小斯坦纳树

约 182 个字 76 行代码 预计阅读时间 2 分钟

给定连通图 G中的 n个点与 k个关键点，连接 k个关键点，使得生成树的所有边的权值和最小。
是一个 nphard 问题

C++

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define LL long long
const int MAXN = 1e5 + 5;
const double EPS = 1e-9;
int n, m, k;
struct edge {
    int v, w, ne;
};
edge e[1000];
int idx, h[200];
void add(int a, int b, int c)
{
    e[idx] = {b, c, h[a]};
    h[a] = idx;
    idx++;
}
int dp[200][5000];
int key[20];
struct Polar {
    int w, u;
    friend bool operator>(const Polar &a, const Polar &b) { return a.w > b.w; }
};
priority_queue<Polar, vector<Polar>, greater<Polar>> q;
void dijstra(int s)
{
    vector<int> vis(n + 1, 0);
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = 1;
        for (int i = h[u]; ~i; i = e[i].ne) {
            int v = e[i].v, w = e[i].w;
            if (dp[v][s] > dp[u][s] + w) {
                dp[v][s] = dp[u][s] + w;
                q.push({dp[v][s], v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(h, -1, sizeof(h));
    memset(dp, INF, sizeof(dp));
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 1; i <= k; i++) {
        cin >> key[i];
        dp[key[i]][1 << (i - 1)] = 0;
    }
    for (int s = 1; s < (1 << k); s++) {
        for (int i = 1; i <= n; i++) {
            for (int sub = (s - 1) & s; sub; sub = (sub - 1) & s) {
                dp[i][s] = min(dp[i][s], dp[i][sub] + dp[i][sub ^ s]);
            }
            if (dp[i][s] != INF) {
                q.push({dp[i][s], i});
            }
        }
        dijstra(s);
    }
    cout << dp[key[1]][(1 << k) - 1] << endl;
    return 0;
}

尝试用 dp[i][s] 表示以 i 为根，包含集合 S 中所有点的最小边权值和。
先合并子树，再利用最短路松弛节点，最后只要以 k 个关键点中的某一个为根，覆盖所有的节点就行了，实际上维护了任意点与 k 个点联通的最小代价

典型题目

G - Minimum Steiner Tree 2