最小斯坦纳树
斯坦纳树问题是组合优化问题，与 最小生成树相似 ，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。 -----百度百科
我们所熟知的最小生成树问题其实就是一种特殊的最小斯坦纳树问题，相当于在所有点之间找到一个最短网络
实现
题目描述：
给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)。
再给定包含 \(k\) 个结点的点集 \(S\)，选出 \(G\) 的子图 \(G'=(V',E')\),使得：
- \(S\subseteq V'\);
- \(G'\) 为连通图
- \(E'\)中所有边的权值和最小
求出 \(E'\) 中所有边的权值和
我们通过状压dp求解最小斯坦纳树
由于处理的是一个树形结构，所以以树形为基础设计状态
设 f[i][S] 表示以 i 为根，当前选出的点集为 S
通过两个部分来转移,一是兄弟节点之间的转移，二是根节点之间的转移
兄弟节点之间的转移我们这样实现
\[ f[i][S] = min( f[i][S], f[i][T] + f[i][S-T] ); \]其中 T 是 S 的子集，这个方程的意思就是将 i 的所有子树合并在一起
对于根节点之间的转移我们这样实现
\[f[i][S] = f[j][s] + w( i, j ) \]即将子树 j 连接到新的根 i 上。
可以发现这个式子和我们最短路中的三角形不等式非常相像，所以只需要跑一个最短路转移即可
代码实现
#include <bits/stdc++.h>
#define ll long long
#define mod 1e9+7
const int MAXN = 101010;
const int inf = 2e9;
using namespace std;
struct edge{
int u, v, w, nxt;
} e[MAXN];
struct node{
int p, w;
bool operator< ( const node x ) const{
return w > x.w;
}
};
int head[MAXN], cnt = 1;
int f[200][2048];
int dis[200], vis[200];
int n, m, k;
priority_queue < node > q;
inline int read( ){
int x = 0 ; short w = 0 ; char ch = 0;
while( !isdigit(ch) ) { w|=ch=='-';ch=getchar();}
while( isdigit(ch) ) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w ? -x : x;
}
void add( int u, int v, int w ){
e[++cnt] = (edge){ u, v, w, head[u] };
head[u] = cnt;
}
void dij( int s ){
memset( vis, 0, sizeof( vis ) );
for( int i = 1; i <= n; i++ ){
dis[i] = f[i][s];
if( dis[i] < inf ) q.push((node){i, dis[i]});
}
while( !q.empty( ) ){
int x = q.top( ).p;
q.pop( );
if( vis[x] ) continue;
vis[x] = 1;
for( int i = head[x]; i; i = e[i].nxt ){
int y = e[i].v;
if( dis[x] + e[i].w < dis[y] ){
dis[y] = dis[x] + e[i].w;
q.push((node){y, dis[y]});
}
}
}
for( int i = 1; i <= n; i++ )
f[i][s] = dis[i];
}
int main( ){
memset( f, 0x3f, sizeof( f ) );
n = read( ); m = read( ); k = read( );
for( int i = 1; i <= m; i++ ){
int x = read( ), y = read( ), z = read( );
add( x, y, z );
add( y, x, z );
}
for( int i = 1; i <= k; i++ ){
int x = read( );
f[x][1 << (i - 1)] = 0;
}
for( int i = 1; i <= n; i++ ) f[i][0] = 0;
for( int s = 0; s < ( 1 << k ); s++ ){
for( int i = 1; i <= n; i++ )
for( int t = s & ( s - 1 ); t; t = s & ( t - 1 ) )
f[i][s] = min( f[i][s], f[i][t] + f[i][t ^ s] );
dij( s );
}
int ans = inf;
for( int i = 1; i <= n; i++ )
ans = min( ans, f[i][(1 << k) - 1] );
cout << ans;
return 0;
}
这里我用的dij，当然SPFA也可以但是慎用