斯坦纳树学习笔记

先开题罢：

旅行

给定一个 \(n\) 个点 \(m\) 条边的带权图，求一个权值和最小的边集的使得 \(\forall i\le k\) 有 \(i\) 与 \(n-i+1\) 联通的权值和。

无解输出 -1.

\(k\le4, 2k\le n\le10000, m\le10000, wi\le 1000, 1 \le ai, bi \le n\)

啊，非常清新的题面，状压也非常显然，但是搞生成树的时候自闭了。

斯坦纳树

首先就是要明白斯坦纳树是有一个平面上的（在 OI 中没什么用的）定义的：

对一个给定点集，求一个点集使得两个点集的并的联通代价（一般是两点距离，也可能是距离乘上权重等等乱七八糟的东西）。

比如这样：

但是，大部分时候我们并不关心这个定义。

关于上面问题的解：

在给定 \(n\) 个点的情形，最多将有 \(n-2\) 个复接点（斯坦纳点）。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成 \(120^{\circ}\) 角；若为两条边，则此斯坦纳点必为某一已给定的点，且此两条边交成的角必大于或等于 \(120^{\circ}\)。

——摘自 OI Wiki

图论上的斯坦纳树

给定 \(n\) 个点 \(m\) 条边的带权图，与 \(k\) 个关键点，求一个权值和最小的边集的使得 \(\forall i\le k\) 有 \(i\) 与 \(n-i+1\) 联通的权值和。

以下任何表述省略“在图中”。

与引入的问题不能说是十分相似，只能说是完全就是

首先，我们先定义一个 \(f(i,S)\) 表示以 \(i\) 为根的包含了 \(S\) 这个集合中的关键点的最小生成树。

然后，嗯，我们要定义一些转移：

1. \(f(i,S)=\min(f(i,S),f(i,S-T)+f(i,T))\)
2. \(f(i,S)=min(f(i,S),f(j,S)+dis(i,j))\) 其中 \(dis(i,j)\) 定义为 \(i\) 到 \(j\) 的最短路

感性理解一下，第一条转移式就是把点集拼一起，第二条转移式就是把往树里加一条链。

这个比较显然的答案不会小于答案。所以就是正确的，至于为什么不会大于我也不知道

初始值把每个关键点自己生成自己设为 \(0\) 就行。

转移显然最短路。

原问题

显然先把斯坦纳树生成出来，然后把在原题中合法的若干状态拼成全集就行。

CODE

#include
#include
#include
#define reg register
#define uni unsigned
#define ll long long
using namespace std;
const int N=10010,FSIZE=1<<26,W=4,INF=0x3f3f3f3f;
int n,m,k,r,a[N],b[N+N][3],last,g[N][2048],h,t,d[N<<3],map[N],ans=INF;
bool leg[N];
char BuF[FSIZE],*InF=BuF;
int read(){
    reg int x=0;
    for(;47>*InF||*InF>58;++InF);
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    return(x);
}
void add(reg int x,reg int y,reg int w){
    b[++last][0]=a[x];
    b[a[x]=last][1]=y;
    b[last][2]=w;
}
void change(reg int &x,reg int &y){
    swap(map[x],map[y]);
    swap(x,y);
}
void push(reg int nxt,reg int s){
    if(!map[nxt]){
        d[map[nxt]=++t]=nxt;
        if(t>h+1&&g[d[t-1]][s]g[*zh][s]){
                change(hd,*zh);
            }
            if(g[hd][s]>g[*tl][s]){
                change(hd,*tl);
            }
        }
        for(reg int i=a[hd];i;i=b[i][0]){
            reg int nxt=b[i][1],p=g[hd][s]+b[i][2];
            if(g[nxt][s]>p){
                g[nxt][s]=p;
                push(nxt,s);
            }
        }
        map[hd]=0;
    }
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    n=read();m=read();
    for(r=1<<(k=read());m;--m){
        reg int x=read(),y=read(),w=read();
        add(x,y,w);
        add(y,x,w);
    }
    memset(g,63,sizeof(g));
    for(reg int i=0;i