Warning: session_start(): open(/tmp/sess_8805d84a821b74f9d167571e36a5ed5e, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 最小斯坦纳树 ======
===== 算法简介 =====
一种用于计算只含图中部分关键节点的最小生成树的算法。
===== 算法实现 =====
考虑状压 $\text{dp}$，第一维表示当前包含节点的点集，第二维表示树根节点。考虑两步转移
$$
\text{dp}(s,u)\gets \min_{k\subset s}(\text{dp}(k,u)+\text{dp}(s\oplus k,u))
$$
$$
\text{dp}(s,u)\gets \min(\text{dp}(s,u),\text{dp}(s,v)+w)
$$
时间复杂度据说是 $O(2^kn^3+3^kn)$。
===== 算法模板 =====
==== $\text{spfa}$ 版本 ====
namespace SteinerTree{
int n,k,dp[1<q;
_rep(i,1,n){
if(dp[S][i]!=Inf){
q.push(i);
inque[i]=true;
}
}
while(!q.empty()){
int u=q.front();q.pop();
inque[u]=false;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(dp[S][u]+edge[i].w
==== $\text{dijkstra}$ 版本 ====
namespace SteinerTree{
int n,k,dp[1<,vector >,greater > >q;
_rep(i,1,n){
vis[i]=false;
if(dp[S][i]!=Inf)
q.push(make_pair(dp[S][i],i));
}
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(dp[S][u]+edge[i].w
===== 算法习题 =====
==== 习题一 ====
[[https://www.luogu.com.cn/problem/P6192|洛谷p6192]]
=== 题意 ===
给定一个图，图中有 $p$ 个关键点，每个关键点有一个类型 $c_i$，求一个边权最小的子图使得要求所有 $c_i$ 相同的关键点连通。
=== 题解 ===
先对所有关键点跑一遍最小斯坦纳树，接下来设 $g(s)$ 表示类型集合二进制表示为 $s$ 的所有关键点连通的最小费用。
设 $s'$ 表示所有 $1\le i\le p$ 且 $c_i\in s$ 构成的集合的二进制表示，则 $g(s)$ 的初始值为 $\min_{1\le u\le n}dp(s',u)$
接下来跑一遍 $g(s)\gets \min_{k\subset s}(g(k)+g(s\oplus k))$ 即可，时间复杂度等于最小斯坦纳树时间复杂度。
const int MAXN=1005,MAXM=3005,MAXK=10,Inf=1e9;
int head[MAXN],edge_cnt,key_node[MAXK];
struct Edge{
int to,next,w;
}edge[MAXM<<1];
void Insert(int u,int v,int w){
edge[++edge_cnt]=Edge{v,head[u],w};
head[u]=edge_cnt;
}
namespace SteinerTree{
int n,k,dp[1<q;
_rep(i,1,n){
if(dp[S][i]!=Inf){
q.push(i);
inque[i]=true;
}
}
while(!q.empty()){
int u=q.front();q.pop();
inque[u]=false;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(dp[S][u]+edge[i].w Node[MAXK];
int g[1<>j)&1) _for(k,0,Node[j].size())
s|=(1<