斯坦纳树学习笔记

先开题罢：

旅行

给定一个 个点 条边的带权图，求一个权值和最小的边集的使得 有 与 联通的权值和。

无解输出 -1.

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

斯坦纳树

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

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

比如这样：

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

关于上面问题的解：

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

——摘自 OI Wiki

图论上的斯坦纳树

给定 个点 条边的带权图，与 个关键点，求一个权值和最小的边集的使得 有 与 联通的权值和。

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

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

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

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

  2. 其中 定义为 到 的最短路

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

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

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

转移显然最短路。

原问题

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

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<iostream>
#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[d[t]][s]){
            change(d[t],d[t-1]);
        }
    }else if(g[nxt][s]<g[d[t]][s]){
        change(d[map[nxt]],d[t]);
    }
}
void spfa_PMF(int s){
    for(;h<=t;++h){
        reg int &hd=d[h];
        for(reg int i=0,*zh=d+h+1,*tl=d+t;i<W&&zh<tl;++i,++zh,--tl){
            if(g[hd][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<k;g[read()][1<<i++]=0);
    for(reg int i=1;i<r;++i){
        h=0;t=-1;
        for(reg int j=1;j<=n;++j){
            for(reg int k=i&(i-1);k;k=i&(k-1)){
                g[j][i]=min(g[j][i],g[j][k]+g[j][i^k]);
            }
            if(g[j][i]<INF){
                push(j,i);
            }
        }
        spfa_pmf(i);
    }
    for(reg int i=0;i<n;ans=min(ans,g[++i][r-1]));
    printf("%d",ans);
    return(0);
}
≡