斯坦纳树

notes

概述

使关键点连通的最小树。

【模板】最小斯坦纳树

考虑状压 DP，记 $f(u,S)$ 为以 $u$ 为根，包含 $S$ 集合的特殊点的最小树。

将最终的树找出来，对于度数为 $1$ 的点，需要加边，即 $f(u,S) \gets f(v,S) + w$。还需要合并，即 $f(u,S) \gets f(u,S’)+f(u,S \oplus S’)(S’ \subset S)$。

第一种转移用最短路，第二种转移枚举子集。

时间复杂度 $O(n3^n+nm2^n)/O(n3^n+m\log m2^n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;

#define ar(x) array<int,x>
#define pb push_back
const int N=100+10,M=500+10,L=(1<<10)+10,INF=1e9;
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,K,vis[N],f[L][N];
vector<ar(2)> G[N]; queue<int> q;

int main(){
	
	n=rd,m=rd,K=rd;
	for(int i=1,x,y,z;i<=m;++i) G[x=rd].pb({y=rd,z=rd}),G[y].pb({x,z});
	for(int S=0;S<(1<<K);++S) for(int i=1;i<=n;++i) f[S][i]=INF;
	for(int i=1,x;i<=K;++i) x=rd,f[1<<(i-1)][x]=0;
	
	for(int S=0;S<(1<<K);++S){
		for(int T=S;T;T=(T-1)&S) for(int i=1;i<=n;++i) f[S][i]=min(f[S][i],f[T][i]+f[S^T][i]);
		for(int i=1;i<=n;++i) if(f[S][i]!=INF) q.push(i),vis[i]=1;
		while(!q.empty()){
			int u=q.front(); q.pop(),vis[u]=0;
			for(auto [v,w]:G[u]) if(chkmin(f[S][v],f[S][u]+w)&&!vis[v]) q.push(v),vis[v]=1;
		}
	}
	
	int ans=INF; for(int i=1;i<=n;++i) ans=min(ans,f[(1<<K)-1][i]); printf("%d\n", ans);
	
	return 0;
}

例题

1.[JLOI2015] 管道连接

最终答案为斯坦纳森林。先求任意子集的斯坦纳树，再套个状压 DP 即可。

参考

斯坦纳树