最小斯坦纳树

前言

我不太喜欢写板子，但是这个东西的状压 DP 太有启发性了。

问题简述

一个无向图 \(G = (V, E)\) 关于点集 \(S\subseteq V\) 的斯坦纳树定义为 \(G\) 的一个子图 \(G' = (V', E')\) 满足：

1. \(G'\) 联通
2. \(S\subseteq V'\)

求最小斯坦纳树，即给定边权 \(f: E\mapsto \mathbb R^+(\mathbb Z^+)\)，最小化斯坦纳树所有边的边权和。斯坦纳树不一定是树，但是最小斯坦纳树一定是树。

做法

首先一个朴素做法：\(f_T\) 表示关于 \(T\) 的最小斯坦纳树。初始的时候把所有边加进去，然后每次枚举一个公共点，尝试合并两个集合。时间复杂度 \(\Theta(n3^n)\)。实在是烂到家了，比不过枚举点集跑最小生成树的 \(\Theta(m\log m+2^nm\alpha(n))\)。

但是我会优化！注意到，我们不关心 \(S\) 以外的那些点都有谁被连通了，只是利用它们去连那些 \(S\) 里的点。所以设 \(f_{i, T}\) 表示 \(\{i\}\cup T\) 的最小斯坦纳树。那么转移有两种：不改变 \(i\)，把 \(T\) 枚举子集进行合并，没有代价。\(i\) 变成 \(j\)，\(T\) 不变，代价是最短路。时间复杂度是 \(\Theta(n3^{|S|} + \min((m\log m)2^{|S|}, n^22^{|S|} + n^3))\)。反正自己想出来非常困难。