给定 \(k\) 个关键点必须选,选一些点,选一些边连接他们,求总边权最小。
首先最终肯定选出一棵树。看到 \(k\) 的范围,果断状压。
\(dp[i][S]\) 表示以 \(i\) 为根,至少(不是恰好)包含 \(S\) 中的关键点的最小边权总和。
如果最终的树中 \(i\) 的度数 \(>1\),考虑把树分成两个树,各自包含不同的关键点:
\(dp[i][S]\leftarrow \min(dp[i][S],dp[i][T]+dp[i][S-T]).\)
\(T\) 是枚举的 \(S\) 的一个真子集。
否则,就考虑 \(i\) 唯一连着的结点 \(j\):
\(dp[i][S]\leftarrow \min(dp[i][S],dp[j][S]+w(j,i)).\)
我们发现,这个式子和求最短路的松弛式子意外的相似:
\(dist(v)\leftarrow \min(dist(v),dist(u)+w(v,u)).\)
我们可以通过求最短路的方式求。我们可以在每次从队列中取出 \(i\) 这个结点,然后拓展 \(i\) 的所有邻点。
详见代码注释。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
int n, m, k;
struct edge {
int to, next, w;
} e[maxn << 1];
int head[maxn << 1], tree[maxn << 1], tot;
int dp[maxn][5000], vis[maxn];
int key[maxn];
priority_queue<P, vector<P>, greater<P> > q;
void add(int u, int v, int w) {
e[++tot] = edge{v, head[u], w};
head[u] = tot;
}
void dijkstra(int s) {
// 求解最短路,注意这里的S是给定的状态,dijkstra应当只更新dp[x][s],真正的起点已经在调用之前塞进队列里了
memset(vis, 0, sizeof(vis));
while (!q.empty()) {
P item = q.top();
q.pop();
if (vis[item.second]) continue;
vis[item.second] = 1;
for (int i = head[item.second]; i; i = e[i].next) {
if (dp[tree[i]][s] > dp[item.second][s] + e[i].w) {
//如果tree[i]这个点当作根只有item.second(通过i拓展了若干次的结点得到item.second) 这一个儿子,
//那么根据状态转移式,可以用dp[item.second][s]尝试更新dp[tree[i]][s]
//注意这里即使使用了s之外的关键点为根也无所谓——我们定义的dp是至少不是恰好
dp[tree[i]][s] = dp[item.second][s] + e[i].w;
q.push(P(dp[tree[i]][s], tree[i]));
}
}
}
}
int main() {
memset(dp, INF, sizeof(dp));
scanf("%d %d %d", &n, &m, &k);
int u, v, w;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
tree[tot] = v;
add(v, u, w);
tree[tot] = u;
}
for (int i = 1; i <= k; i++) {
scanf("%d", &key[i]);
dp[key[i]][1 << (i - 1)] = 0; //dp初值
}
for (int s = 1; s < (1 << k); s++) {
for (int i = 1; i <= n; i++) {
for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) { //子集枚举,复杂度 O(3^n)
dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]); //第一个转移式子
}
if (dp[i][s] != INF) q.push(P(dp[i][s], i)); //如果连起点都到达不了就不必要了(注意这里提前放好起点)
}
dijkstra(s); //拓展,dp[i][S]能尝试更新所有 dp[x][S],x是任意i可达的结点
}
printf("%d\n", dp[key[1]][(1 << k) - 1]); //其实这里根取哪个关键点都无所谓
return 0;
}
标签:vis,item,int,tree,最小,斯坦纳,second,dp
From: https://www.cnblogs.com/FLY-lai/p/18000602