斯坦纳树

• 给定n个点，试求连接此n个点，总长最短的直线段连接系统，并且任意两点都可由系统中的直线段组成的折线连接起来。

• 模板题：无向连通图,可能自环和重边，给定k个关键点，求一个子图使得边权和最小。

• 分析

  • 子图一定是树，否则一定可以去环使得边权和变小。这棵树就是最小斯坦纳树。
  • 设$dp(i,S)$ 表示$i$ 为根，包含点集$S$ 中所有点的最小权值和
  • 设$T$ 是$S$ 的子集，则$dp(i,S)$ 由$dp(i,T)+dp(i,S-T)$ 转移而来。
  • 松弛操作，对于$i$ 的相邻节点$j$ ：$f(i,S)=min(f(i,S),f(j,S)+w(j,i))$

• 整体步骤

  • 将$dp$ 初始化为$0x3f3f3f3f$
  • 枚举给定点的子集$S$
    • 对于$S$ 枚举子集$T$ ，更新每个节点的$dp$
    • 如果权值和被更新，说明这个点可行，加入$spfa$ 的队列
    • 进行$spfa$ 更新队列中点的相邻点的答案
  • 答案是给定点中的任意点$i$ 的$dp$ 值

for (int i = 0; i < k; i++)
{
	read(p[i]);
	dp[p[i]][1 << i] = 0;
}
int up = (1 << k) - 1;
for (int s1 = 0; s1 <= up; s1++) //枚举给定点的子集递推
{
	for (int i = 1; i <= n; i++)
	{
		for (int s2 = s1 & s1 - 1; s2; s2 = s2 - 1 & s1)			//枚举当前点集的子集
			dp[i][s1] = min(dp[i][s1], dp[i][s2] + dp[i][s1 ^ s2]); //dp(i,S)<-dp(i,T)+dp(i,S_T)
		if (dp[i][s1] < INF)
		{
			q.push(i);
			vst[i] = true;
		}
	}
	spfa(s1); 
}
//spfa里的松弛操作：
// if (dp[v][S] > dp[u][S] + w)
// {
// 	dp[v][S] = dp[u][S] + w;
// 	if (!vst[v]) //如果不在队列里就加入
// 		q.push(v), vst[v] = true;
// }

模板题传送门：洛谷P6192 【模板】最小斯坦纳树
例题传送门：洛谷P4294 [WC2008]游览计划