模板：斯坦纳树

前言

小清新的算法。
称之为算法感觉有些牵强，因为其能够解决的问题实在是太单一了，甚至像是一道题的题解。

卷是不可能卷的，只是摸鱼的时候无意路过讲这个的博客，发现很好写，手痒就给写了。
下不为例

问题

给出一个无向图并指定若干特殊点，求一个联通的导出子图，使得其包含所有特殊点，且边权和最小。

解析

首先应该不难发现一些显然但有用的性质：

1. 最终的答案必然为一棵树。
2. 叶子必然是特殊点。

（然而好像第二条没啥用）。
考虑利用第一条 dp：
$f_{i,s}$ 表示以 $i$ 为根的生成树，包含关键点状态为 $s$ 的最小花费。
转移：
$f_{i,s}\leftarrow f_{i,t}+f_{i,s/t}(t\subset s)$
$f_{i,s}\leftarrow f_{j,s}+e_{j,i}$
不难发现任何合法解都可以通过这些转移得到。
然后就做完了。
第一条转移暴力枚举子集，第二条在每一层跑迪杰斯特拉即可。
时间复杂度 $O(n{3}^k+m\log m{2}^k)$。

代码

由于懒用邻接矩阵结果复杂度似乎变成 $O(n{3}^k+(n^2+m\log m)2^k)$ 了…
但是依然跑的飞快，所以懒得改了

#include
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("line: %d\n",__LINE__)

inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=105;
const int S=1050;
const int inf=1e9;
const bool Flag=0;
const int mod=998244353;

inline ll ksm(ll x,ll k){
  ll res(1);
  while(k){
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n,m,k;
int e[N][N];
int dp[N][S],mi[20],id[N];
#define pr pair<int,int>
#define mkp make_pair
priority_queue<pr,vector<pr>,greater<pr> >q;
bool vis[N];
void dij(int s){
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++) q.push(mkp(dp[i][s],i));
  while(!q.empty()){    
    int x=q.top().second;q.pop();
    if(vis[x]) continue;
    vis[x]=1;
    for(int i=1;i<=n;i++){
      if(dp[i][s]>dp[x][s]+e[x][i]){
	dp[i][s]=dp[x][s]+e[x][i];
	q.push(mkp(dp[i][s],i));
      }
    }
  }
  return;
}

int main(){

  //freopen("a.in","r",stdin);
  //freopen("a.out","w",stdout);

  memset(dp,0x3f,sizeof(dp));
  memset(e,0x3f,sizeof(e));
  memset(id,-1,sizeof(id));
  n=read();m=read();k=read();
  for(int i=1;i<=m;i++){
    int x=read(),y=read(),w=read();
    e[x][y]=e[y][x]=min(e[x][y],w);
  }
  mi[0]=1;
  for(int i=1;i<=k;i++){
    mi[i]=mi[i-1]<<1;
    id[read()]=i-1;
  }
  for(int i=1;i<=n;i++){
    if(id[i]!=-1) dp[i][mi[id[i]]]=0;
    dp[i][0]=0;
  }
  for(int s=1;s<mi[k];s++){
    for(int i=1;i<=n;i++){
      for(int t=s;t;t=(t-1)&s) dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s-t]);
    }
    dij(s);
  }
  int ans=2e9;
  for(int i=1;i<=n;i++) ans=min(ans,dp[i][mi[k]-1]);
  printf("%d\n",ans);
  return 0;
}

/*
*/

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
84
85
86
87
88
89