最小 Steiner 树学习笔记
stripe_python · · 题解
问题 给定带权无向连通图
这个问题被称作最小 Steiner 树,可以证明是 NP-Hard 的。
性质 最优子图必然是树。
证明 若子图有环,任意删去环上一条边,边权和减小且仍然合法。
设
- 枚举
T \subset S ,将T 和S \setminus T 在u 处合并,转移f_{u,S} \gets f_{u,T} + f_{u,S \setminus T} 。 - 从
v 继承连通性,转移f_{u,S} \gets f_{v,S}+\text{dis}(u,v) 。其中\text{dis}(u,v) 为最短路。
注意转移顺序是,外层按二进制序枚举
DP 初值
容易 Floyd 做到
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;
}