「OI」斯坦纳树 Steiner Tree

斯坦纳树 问题是组合优化问题，与最小生成树相似，是最短网络的一种。

斯坦纳树问题

内容

一个有 \(n\) 个点 \(m\) 条边的有权无向图，然后选定 \(k\) 个点，让你求出使这 \(k\) 个点联通所需的最小代价，其实最小生成树是最小斯坦纳树的一种特殊情况（\(n=k\)）。

斯坦纳树问题本质上就是一个状压 \(\texttt{DP}\) 的过程。

斯坦纳树

由来

不难发现，斯坦纳树问题最后得到的连通块一定是一棵树，所以问题的答案又称为斯坦纳树。

具体思路

为了解决斯坦纳树问题，我们考虑状压 \(\texttt{dp}\)。设 \(f _ {i, S}\) 表示以 \(i\) 为根，包含选定点的状态为 \(S\) 的情况下所需要的代价的最小值，其中当 \(S\) 在二进制下的第 \(i\) 位为 \(1\) 时表示包含了第 \(i\) 个关键点，为 \(0\) 则表示不包含。

那么我们可以得出我们的第一个转移式：

\[f _ {i,S}=\min _ {\text{sub}\subset S}\{f _ {i,\text{sub}}+f _ {i,S-\text{sub}}\}\]

这条转移式就是将 \(S\) 拆分成 \(\text{sub}\) 和 \(S-\text{sub}\) 两个状态，其中 \(\text{sub}\subset S\)。

我们已经解决了自己更新自己的问题了，那么我们怎么解决新加一条边的问题呢？

我们又可以想到下面的这条转移式：

\[f _ {i, S}=\min\{f _ {j, S}+\text{val} _ {j,i}\}\]

然后发现它的形式与求最短路的松弛形式一致（把 \(S\) 忽略），所以我们可以使用 \(\texttt{Dijkstra}\) 或者 \(\texttt{SPFA}\) 来处理这个问题。

简单实现

下面是 \(\texttt{Dijkstra}\) 版的，要比 \(\texttt{SPFA}\) 的慢一点。

struct Node{
	int id,dis;
	inline Node(reg int id=0,reg int dis=0):id(id),dis(dis){
		return;
	}
	inline bool operator<(const Node& a)const{
		return dis<a.dis;
	}
	inline bool operator>(const Node& a)const{
		return dis>a.dis;
	}
};

bool vis[MAXN];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;

inline void Dijkstra(reg int s){
	memset(vis,false,sizeof(vis));
	while (!Q.empty()){
		reg int id=Q.top().id;
		Q.pop();
		if(vis[id])
			continue;
		vis[id]=true;
		for(reg int i=head[id];i;i=Next[i]){
			reg int v=to[i];
			if(dp[v][s]>dp[id][s]+w[i]){
				dp[v][s]=dp[id][s]+w[i];
				Q.push(Node(v,dp[v][s]));
			}
		}
	}
	return;
}

void Solve(void){
	memset(dp,0X3F,sizeof(dp));
	for(reg int i=1;i<=k;++i)
		dp[p[i]][1<<(i-1)]=0;
	for(reg int S=1;S<(1<<k);++S){
		for(reg int i=1;i<=n;++i){
			for(reg int sub=S&(S-1);sub;sub=S&(sub-1))
				dp[i][S]=min(dp[i][S],dp[i][sub]+dp[i][S^sub]);
			if(dp[i][S]!=INF)
				Q.push(Node(i,dp[i][S]));
		}
		Dijkstra(S);
	}
	return;
}

例题

• 「题解」「WC2008」游览计划 trip；
• 「题解」挖宝藏 treasure。

参考资料

• 斯坦纳树学习笔记 – abcdeffa 的博客 – 洛谷博客；
• [学习笔记]斯坦纳树 – *Miracle* – 博客园。