Luogu6192 【模板】最小斯坦纳树

tony102

2021 年 09 月 07 日

1976 次浏览

暂无评论

860字数

题解

[Link](https://www.luogu.com.cn/problem/P6192)

## Sol

点集 $S$ 的大小 $\leq 10$ ，可以是试一试状压。

首先很显然的一件事就是，答案一定构成一棵树。设想一下，加入答案是个环，断掉环上一条边变成一棵树，仍然保持连通并且因为边权 $> 0$ 所以权值和一定会变小。

设 $f_{i, s}$ 表示以 $i$ 为根的子树，选的点集为 $s$ 的最小权值和。

考虑转移，分为两种情况。一种是该点的度数为 $1$ ，第二种是度数 $> 1$。

第一种情况转移相对简单，枚举 $i$ 的每一个通过出边到达的点：

$f(j,s) + w(i,j) \to f(i,s)$

第二种情况，将 $i$ 下面挂的点分成若干棵子树考虑转移：

$f(i, t) + f(i, s - t) \to f(i,s) (t \subseteq s)$

枚举子集转移即可。

枚举每一种状态，每个状态跑最短路即可。时间复杂度：$O(n\cdot3^{k} + m \log m \cdot 2^{k})$

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef pair < int, int > PII;
const int SIZE = 1e2 + 5;
const int inf = 0x7f;

int n, m, k, num;
int head[SIZE], S[SIZE], vis[SIZE], f[SIZE][(1 << 10) + 5];
std::priority_queue < PII > q;

struct node {
	int to, v, nxt;
} edge[1005];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void addEdge(int u, int v, int d) {
	edge[++ num] = (node) {v, d, head[u]}, head[u] = num;
}

void dijkstra(int s) {
	memset(vis, 0, sizeof(vis));
	while (!q.empty()) {
		PII h = q.top(); int u = h.second; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u], v; i; i = edge[i].nxt) {
			v = edge[i].to;
			if (f[v][s] > f[u][s] + edge[i].v) 
				f[v][s] = f[u][s] + edge[i].v, q.push((PII) {-f[v][s], v});
		}
	}
}

int main() {
	n = read(), m = read(), k = read();
	for (int i = 1, u, v, d; i <= m; ++ i) {
		u = read(), v = read(), d = read();
		addEdge(u, v, d), addEdge(v, u, d);
	}
	memset(f, inf, sizeof(f));
	for (int i = 1; i <= k; ++ i) {
		S[i] = read(); f[S[i]][1 << (i - 1)] = 0;
	}
	for (int s = 1; s < (1 << k); ++ s) {
		for (int i = 1; i <= n; ++ i) {
			for (int t = s & (s - 1); t; t = s & (t - 1)) 
				f[i][s] = std::min(f[i][s], f[i][t] + f[i][s ^ t]);
			if (f[i][s] != f[0][0]) q.push((PII) {-f[i][s], i});
		}
		dijkstra(s);
	}
	printf("%d\n", f[S[1]][(1 << k) - 1]);
	return 0;
}
```

最后修改：2021 年 09 月 07 日