【模板】斯坦纳树
模拟赛出了一个斯坦纳森林的题，全军覆没。
于是赶紧过来学习。
\(1.\)概述
先来看这道题：一张无向图，求它的最小生成树。
不会有人不会吧，Kruskal或者Prim一下就好了。
然后是它的进阶版：
一张无向图 \(G\)，\(|V| \leq 100,|E| \leq 500\)，给定一个大小为 \(k(k \leq 10)\) 集合 \(S\)，求一个子图 \(G'(V',E')\)，使得 \(S?V',G'\) 连通，且最小化 \(E'\) 权值和。
可以发现最小生成树就是 \(S=V\) 时的特殊情况。那么这个东西怎么做呢？
\(2.\)解法
首先，\(G'\) 一定是一颗树。
要不然如果有环的话随便断掉一条边还是符合的。
于是我们钦定一个树根，设 \(dp[i][mask]\) 表示以 \(i\) 为根的一棵树，包含了 \(mask\) 中所有点的最小权值（\(mask\) 是状压 \(S\) 中的点，所以 \(i\)可能不在 \(mask\) 中）。
然后转移的时候分两种情况：
- 树中 \(i\) 的度不为 1。
那么一定可以将 \(mask\) 分为两个子集 \(s,mask-s\)，使得它们代表的集合分别在 \(i\) 的两个不同的子树中。
但我们不知道 \(s\) 是什么，于是我们考虑暴力，用 \(O(3^k)\) 的复杂度枚举子集，暴力转移。
所以有
\[dp[i][mask]=\min_{s?mask}dp[i][s]+dp[i][mask-s] \]- 树中\(i\) 的度为 1。
那么这时与 \(i\) 相邻的那个点 \(j\) 的答案加上 \(dis(i,j)\) 一定比 \(i\) 优。
但是我们仍然不知道 \(j\) 是那个点，也不知道哪些 \(i\) 度为 1，于是我们继续考虑暴力，用 \(O(n^2)\) 的复杂度枚举两个点，暴力转移。
所以又有
\[dp[i][mask]=\min_{j=1}^n dp[j][mask]+dis[i][j] \]可以证明，只有 \(i,j\) 相邻时 \(dp[i][mask]\) 会改变。
于是做完了。
注意事项：
\(dis[i][j]\) 的求法可以 \(O(n^3)Floyd\)。
总复杂度 \(O(n^3+n^2 \times 2^k + n \times 3^k)\)
例题：
1.【模板】最小斯坦纳树
就是板子。
\(Code:\)
// Problem: P6192 【模板】最小斯坦纳树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6192
// Memory Limit: 250 MB
// Time Limit: 1000 ms
#include
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i
inline ll rd() {
ll x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x*f;
}
#define d rd()
#define pb push_back
const ll N=300010;
ll dis[110][110];
ll qp(ll a,ll b,ll p){
ll ans=1;while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;b>>=1;
}return ans;
}ll n,m,k;
ll s,dp[110][2010];
int main(){
memset(dis,0x3f,sizeof(dis));
n=d,m=d,k=d;
f(i,1,m){
ll u=d,v=d,w=d;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}f(kk,1,n)f(i,1,n)f(j,1,n)dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);
memset(dp,0x3f,sizeof(dp));
f(i,1,k)s=d,dp[s][1<<(i-1)]=0;
f(msk,0,(1< 2.Ticket to Ride
题意：一张图，给定 4 对关键点（一共 8 个点）,求最小斯坦纳森林。
发现按照上面的那样做不行，因为这个不用保证所有点连通。
因为所有的点都是按照顺序读进来的，所以只有第一对点在 \(mask\) 中连通表示为 \((00000011)_2\)，只有第二对点表示为 \((00001100)_2\)，第一对和第二对同时连通为 \((00001111)_2\)。
所以只有 \(mask[0]\)（表示 \(mask\) 的第 0 位）\(=mask[1],mask[2]=mask[3].mask[4]=mask[5],mask[6]=mask[7]\) 时这个 \(mask\) 合法。
然后就可以写一个 check 来判断是否合法。
我们再设一个数组 \(f[mask]\)，表示合法的 \(mask\) 状态的点对分别连通时的最小权值。
所以一开始 \(f[mask]=\min_{i=1}^n dp[i][mask]\)。
假设 \(mask=(11001111)_2\)，所以
\[f[11001111]=\min(f[11000000]+f[00001111],f[11001100]+f[00000011],f[11000011]+f[00001100]) \]于是可以发现
\[f[mask]=\min_{s?mask 且s合法}f[s]+f[mask-s] \]于是又是一个枚举子集。
然后好了。
\(Code:\)
// Problem: Ticket to Ride
// Contest: POJ - Northwestern Europe 2006
// URL: http://poj.org/problem?id=3123
// Memory Limit: 65 MB
// Time Limit: 2000 ms
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
[WC2008]游览计划还有Garden
都是板子，加个输出方案就行了。