斯坦纳树

引入

众所周知，最小生成树是用来解决图上最小代价联通的问题的，但是他有一个局限性，那就是他仅适用于必须将所有点全部联通的情况。

有一类问题，需要求图上联通所有关键点的最小代价，在这种情况下，之前的最小生成树的策略显然不适用，因为不必连接所有点，但又可能会存在一些中转点，看起来非常的凌乱，这个时候，就需要用到斯坦纳树

模板

题目描述

这是斯坦纳树的经典例题，题面就不过多赘述，解决这一问题，我们考虑$dp$，状压并不好办，因为节点数太多，但是发现关键点数并不多，于是设计出来$dp$数组为$f_{p,s}$，其中$p$表示指定为树根的节点下标，$s$为当前树对关键点的包含状态，数组存的值，即为最小代价，

可是我们发现，这图显然不是$DAG$，那没有拓扑序怎么$dp$呢，这时候可以用最短路的思想来协助$dp$,如同最短路的更新操作，我们可以使用一个点的$dp$值来更新其他点的$dp$值，同时，还有针对于同根的子树的合并更新

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> P;
ll n,m,k,key[15],head[105],cnt=1,dp[105][2000];
struct edge{
    ll to,next,w;
}e[1005];
struct node{
    ll val,pos;
    bool operator <(const node &a)const{
        return val>a.val;
    }
}tmp;
void make(ll u,ll v,ll w){
    e[cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt++;
}
priority_queue<node> q;
void dij(ll s){//这是类最短路松弛更新
    while(!q.empty()){
        tmp=q.top();
        q.pop();
        ll p=tmp.pos;
        if(tmp.val<dp[p][s])continue;
        for(int i=head[p];i;i=e[i].next){
            if(dp[p][s]+e[i].w<dp[e[i].to][s]){
                dp[e[i].to][s]=dp[p][s]+e[i].w;
                tmp.pos=e[i].to;
                tmp.val=dp[e[i].to][s];
                q.push(tmp);
            }
        }
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ll u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        make(u,v,w);
        make(v,u,w);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=(1<<k);j++){
            dp[i][j]=1e18;
        }
    }
    for(int i=1;i<=k;i++){
        scanf("%lld",&key[i]);
        dp[key[i]][1<<(i-1)]=0;
    }
    for(int i=1;i<(1<<k);i++){
        for(int j=1;j<=n;j++){
            for(int o=(i-1)&i;o;o=(o-1)&i){
                dp[j][i]=min(dp[j][i],dp[j][o]+dp[j][i^o]);//这是合并更新
            }
            if(dp[j][i]!=1e18){tmp.pos=j,tmp.val=dp[j][i],q.push(tmp);}
        }
        dij(i);
    }
    printf("%lld",dp[key[1]][(1<<k)-1]);
    return 0;
}