斯坦纳树 问题是组合优化问题，与最小生成树相似，是最短网络的一种。
斯坦纳树问题
内容
一个有 \(n\) 个点 \(m\) 条边的有权无向图，然后选定 \(k\) 个点，让你求出使这 \(k\) 个点联通所需的最小代价，其实最小生成树是最小斯坦纳树的一种特殊情况（\(n=k\)）。
斯坦纳树问题本质上就是一个状压 \(\texttt{DP}\) 的过程。
斯坦纳树
由来
不难发现，斯坦纳树问题最后得到的连通块一定是一棵树，所以问题的答案又称为斯坦纳树。
具体思路
为了解决斯坦纳树问题，我们考虑状压 \(\texttt{dp}\)。设 \(f _ {i, S}\) 表示以 \(i\) 为根，包含选定点的状态为 \(S\) 的情况下所需要的代价的最小值，其中当 \(S\) 在二进制下的第 \(i\) 位为 \(1\) 时表示包含了第 \(i\) 个关键点，为 \(0\) 则表示不包含。
那么我们可以得出我们的第一个转移式：
\[f _ {i,S}=\min _ {\text{sub}\subset S}\{f _ {i,\text{sub}}+f _ {i,S-\text{sub}}\}\]
这条转移式就是将 \(S\) 拆分成 \(\text{sub}\) 和 \(S-\text{sub}\) 两个状态，其中 \(\text{sub}\subset S\)。
我们已经解决了自己更新自己的问题了，那么我们怎么解决新加一条边的问题呢？
我们又可以想到下面的这条转移式：
\[f _ {i, S}=\min\{f _ {j, S}+\text{val} _ {j,i}\}\]
然后发现它的形式与求最短路的松弛形式一致（把 \(S\) 忽略），所以我们可以使用 \(\texttt{Dijkstra}\) 或者 \(\texttt{SPFA}\) 来处理这个问题。
简单实现
下面是 \(\texttt{Dijkstra}\) 版的，要比 \(\texttt{SPFA}\) 的慢一点。
struct Node{
int id,dis;
inline Node(reg int id=0,reg int dis=0):id(id),dis(dis){
return;
}
inline bool operator<(const Node& a)const{
return dis<a.dis;
}
inline bool operator>(const Node& a)const{
return dis>a.dis;
}
};
bool vis[MAXN];
priority_queue<Node,vector<Node>,greater<Node>/**/> Q;
inline void Dijkstra(reg int s){
memset(vis,false,sizeof(vis));
while (!Q.empty()){
reg int id=Q.top().id;
Q.pop();
if(vis[id])
continue;
vis[id]=true;
for(reg int i=head[id];i;i=Next[i]){
reg int v=to[i];
if(dp[v][s]>dp[id][s]+w[i]){
dp[v][s]=dp[id][s]+w[i];
Q.push(Node(v,dp[v][s]));
}
}
}
return;
}
void Solve(void){
memset(dp,0X3F,sizeof(dp));
for(reg int i=1;i<=k;++i)
dp[p[i]][1<<(i-1)]=0;
for(reg int S=1;S<(1<<k);++S){
for(reg int i=1;i<=n;++i){
for(reg int sub=S&(S-1);sub;sub=S&(sub-1))
dp[i][S]=min(dp[i][S],dp[i][sub]+dp[i][S^sub]);
if(dp[i][S]!=INF)
Q.push(Node(i,dp[i][S]));
}
Dijkstra(S);
}
return;
}
近期评论