斯坦纳树 问题是组合优化问题,与最小生成树相似,是最短网络的一种。
斯坦纳树问题
内容
一个有 \(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; }
Greetings from Los angeles! I’m bored at work so I decided to check out
your blog on my iphone during lunch break. I enjoy the knowledge you
present here and can’t wait to take a look when I get home.
I’m amazed at how fast your blog loaded on my phone
.. I’m not even using WIFI, just 3G .. Anyways, wonderful
site!