1斯坦纳树和最小生成树相似，最小生成树可以认为是斯坦纳树的特殊情况，主要概念为，有k个关键点，要让它们相连，并且可以连接关键点以外的点，实现边权值值或者是其他权重和最小。
2大多数情况可以用dp写，当关键点少的时候还可以使用状压dp写，主要形式为一个二维数组，可以让第一个元素表示以i为根，第二个元素用状压表示集合（当前选取了哪几个关键点），数组记录当前情况的权值最小和。
3状态转移有可能以下形式：
（1）第一步，对于一个集合S，以及它的自己T，S-T表示T的补集（T和(S-T)构成S），用这两个连通的子集去实现转移：
dp[i][S]=min(dp[i][S],dp[i][T]+dp[i][S-T])
（2）第二步，对于当前集合S，以不同的根节点相互之间实现松弛，就像求最短路一样。
dp[i][S]=min(dp[i][S],dp[j][S]+dis[j][i])
代码实现
根据模板题：
【模板】最小斯坦纳树 – 洛谷
1数据存储
int n,m,k;//n个点，m条边，k个关键点
struct edge{
int to,w;
};
vector<edge>vv[maxn];
inline void add(int u,int v,int w)
{
vv[u].push_back({v,w});
vv[v].push_back({u,w});;
}
int dp[maxn][4200];//假设第一个元素为i，第二个元素为j，表示以i为根的，包含了集合j（状压表示）的所有元素最小权值和
bool vis[maxn];//最短路需要，标记当前点被访问过了
2第一次转移（当前集合中两个联通的子集）
void solve()
{
for(int s=1;s<(1<<k);s++)//枚举各种集合
{
//第一次转移
for(int t=s;t;t=(t-1)&s)//枚举当前集合的所有子集
{
for(int i=1;i<=n;i++)
dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s-t]);//对联通的子集和它的补集进行转移
}
//第二次转移
dij(s);
}
}
3第二次转移（所有根节点相互之间在同样包含S集合情况下）
void dij(int s)//寻找包含集合s（状压表示）以i为根的最小权值和
{
for(int i=1;i<=n;i++)//初始化为0，表示没有访问过
vis[i]=0;
for(int i=1;i<=n;i++)
if(dp[i][s]!=inf)
que.push({dp[i][s],i});
while(!que.empty())
{
node p=que.top();
que.pop();
int id=p.id;
if(vis[id])
continue;
vis[id]=1;
for(int i=0;i<vv[id].size();i++)
{
int to=vv[id][i].to;
int w=vv[id][i].w;
if(dp[to][s]>dp[id][s]+w)//松弛操作
{
dp[to][s]=dp[id][s]+w;
que.push({dp[to][s],to});
}
}
}
}
4主函数
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
for(int s=0;s<(1<<k);s++)
for(int i=1;i<=n;i++)
dp[i][s]=inf;
for(int i=0;i<k;i++)
{
int x;
cin>>x;
dp[x][1<<i]=0;//标记x为关键点集合第i个元素，且以x为根节点只包括子集，权值和为0
}
solve();
int ans=inf;
for(int i=1;i<=n;i++)
ans=min(ans,dp[i][(1<<k)-1]);
cout<<ans<<'\n';
return 0;
}
5完整代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int n,m,k;//n个点，m条边，k个关键点
struct edge{
int to,w;
};
vector<edge>vv[maxn];
inline void add(int u,int v,int w)
{
vv[u].push_back({v,w});
vv[v].push_back({u,w});;
}
int dp[maxn][4200];//假设第一个元素为i，第二个元素为j，表示以i为根的，包含了集合j（状压表示）的所有元素最小权值和
bool vis[maxn];//最短路需要，标记当前点被访问过了
struct node{
int dis,id;//保证优先队列顶部dis最小
friend bool operator <(const node&a,const node&b)
{
return a.dis>b.dis;
}
};
priority_queue<node>que;//最短路算法需要
void dij(int s)//寻找包含集合s（状压表示）以i为根的最小权值和
{
for(int i=1;i<=n;i++)//初始化为0，表示没有访问过
vis[i]=0;
for(int i=1;i<=n;i++)
if(dp[i][s]!=inf)
que.push({dp[i][s],i});
while(!que.empty())
{
node p=que.top();
que.pop();
int id=p.id;
if(vis[id])
continue;
vis[id]=1;
for(int i=0;i<vv[id].size();i++)
{
int to=vv[id][i].to;
int w=vv[id][i].w;
if(dp[to][s]>dp[id][s]+w)//松弛操作
{
dp[to][s]=dp[id][s]+w;
que.push({dp[to][s],to});
}
}
}
}
void solve()
{
for(int s=1;s<(1<<k);s++)//枚举各种集合
{
//第一次转移
for(int t=s;t;t=(t-1)&s)//枚举当前集合的所有子集
{
for(int i=1;i<=n;i++)
dp[i][s]=min(dp[i][s],dp[i][t]+dp[i][s-t]);//对联通的子集和它的补集进行转移
}
//第二次转移
dij(s);
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
for(int s=0;s<(1<<k);s++)
for(int i=1;i<=n;i++)
dp[i][s]=inf;
for(int i=0;i<k;i++)
{
int x;
cin>>x;
dp[x][1<<i]=0;//标记x为关键点集合第i个元素，且以x为根节点只包括子集，权值和为0
}
solve();
int ans=inf;
for(int i=1;i<=n;i++)
ans=min(ans,dp[i][(1<<k)-1]);
cout<<ans<<'\n';
return 0;
}