Reincarnation

正因为梦易碎，才格外美好。

斯坦纳树

发表于 更新于 分类于 ，
本文字数： 7.7k 阅读时长 ≈ 7 分钟

“在最后关头拼尽全力为的，也只有那几个而已了吧……”

介绍

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。

简单来说，斯坦纳树要求我们解决下面这个问题：在一张边带权无向图 中，有 个关键点，要求我们选出一个边集 ，且使得 个关键点两两连通，求权值和最小的 。

容易发现，最终答案一定是一棵包含了 个关键点的一棵树，这棵树就被称为斯坦纳树，权值最小的则称为最小斯坦纳树。

求解

一般而言， 都不会超过 ，而 最多在 范围内，斯坦纳树只有一个复杂度不算优秀的做法（斯坦纳树问题的求解是一个 问题），也是一个骗分常用技巧——状态压缩。

考虑到利用树的性质，定义转移 表示以 为根，当前已经包含了关键点集合为 的最小权值和（ 用二进制位表示）。这里的 是我们定义的，并没有对答案造成过多的影响，只是方便我们进行状态转移。

对于当前集合已经连通的情况，我们可以考虑找到 的一个子集 ，然后：（这是对于子集与子集之间的转移）

然后考虑没有连通的 ，我们先贪心地找到 的最优子解，这里可以考虑最短路，对边进行松弛，转移为：（转移意义类比换根）

。

那这个问题大概就解决了。枚举子集的时间复杂度为 的，松弛操作可以使用 做到 ，总时间复杂度为 。

例题

P6192 【模板】最小斯坦纳树

对于状压的部分用到了位运算的基本技巧——枚举子集，可以记一下。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// ----- Eternally question-----
// Problem: P6192 【模板】最小斯坦纳树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6192
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-29 09:30:56
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e2+10,MAXM=5e2+10,MAXK=11,MAXS=(1<<10)+10;
const int INF=0x3f3f3f3f;
int N,M,K;
struct G
{
	int next,to,val;
}Edge[MAXM<<1];
int Head[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
int Dp[MAXN][MAXS],Pt[MAXK];
bool Vis[MAXN];
inline void Spfa(int s)
{
	std::queue<int>Q;
	for(int i=1;i<=N;++i)
	{
		for(int t=s&(s-1);t;t=(t-1)&s)
			checkMin(Dp[i][s],Dp[i][t]+Dp[i][s^t]);
		if(Dp[i][s]<=INF) Q.push(i),Vis[i]=1;
	}
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;		//这个地方必须要提出来写，写在一起会锅。
			if(checkMin(Dp[v][s],Dp[u][s]+Edge[e].val)&&!Vis[v]) Q.push(v),Vis[v]=1; 
		}
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M,K);
	std::memset(Dp,0x3f,sizeof(Dp));
	for(int i=1,u,v,w;i<=M;++i){ read(u,v,w);addEdge(u,v,w); }
	for(int i=1;i<=K;++i) read(Pt[i]),Dp[Pt[i]][1<<(i-1)]=0;
	for(int s=0;s<(1<<K);++s) Spfa(s);
	int ans=INF;
	for(int i=1;i<=K;++i) checkMin(ans,Dp[Pt[i]][(1<<K)-1]);
	write(ans);
	return 0;
}
/*

*/

JLOI2015 管道连接

题目介绍

题目来源：吉林省选 第二天第二题（貌似？）

评测链接 ：https://www.luogu.com.cn/problem/P3264
评测链接 ：https://loj.ac/p/2110

形式化题意：给定一张 个结点， 条边的无向图，有 个关键点，每个关键点有一个颜色，要求将同种颜色连通所需要的最小边权和。

求解斯坦纳森林的问题。（单纯求解斯坦纳树可以得到 的高分）

因为我们只需要让频道相同的几个结点连接，而不用考虑频道不同的结点，但是斯坦纳树的过程让我们考虑了，所以答案可能会偏大。所以我们考虑把每一个频率都剔出来，用 表示频率为 的结点集合，然后我们暴力枚举每一种集合的选取情况，用 表示在所有结点作根时 的最小答案，用 做二次剔除之后的答案数组，考虑枚举集合 表示的不是关键点的选取情况，而是频率的选取情况，然后做一次状压 即可，数据点好像有点水，不保证正确性。（洛谷和 都能过）

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// ----- Eternally question-----
// Problem: P3264 [JLOI2015]管道连接
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3264
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-29 11:29:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e3+10,MAXM=1e5+10,MAXP=11,MAXS=(1<<10)+10;
const int INF=0x3f3f3f3f;
int N,M,P;
int Dp[MAXN][MAXS];
bool Vis[MAXN];
struct G
{
	int next,to,val;
}Edge[MAXM<<1];
int Head[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
inline void Spfa(int s)
{
	std::queue<int>Q;
	for(int x=1;x<=N;++x)
	{
		for(int t=s&(s-1);t;t=(t-1)&s)
			checkMin(Dp[x][s],Dp[x][t]+Dp[x][s^t]);
		if(Dp[x][s]<INF) Q.push(x),Vis[x]=1;
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		Vis[x]=0;
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(checkMin(Dp[v][s],Dp[x][s]+Edge[e].val)&&(!Vis[v])) Q.push(v),Vis[v]=1;
		}
	}
}
int Freq[MAXP],Pt[MAXP],Id[MAXP];
int Val[MAXS],G[MAXS];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M,P);
	std::memset(Dp,0x3f,sizeof(Dp));
	for(int i=1,u,v,w;i<=M;++i){ read(u,v,w);addEdge(u,v,w); }
	for(int i=1;i<=P;++i) read(Id[i],Pt[i]),Dp[Pt[i]][(1<<(i-1))]=0,Freq[Id[i]]|=(1<<(i-1));
	// for(int i=1;i<=P;++i)
		// for(int j=i+1;j<=P;++j)
			// for(int x:Freq[i])
				// for(int v:Freq[j])
					// addEdge(x,v,0),write(x,' ',v,'\n');
	for(int s=0;s<(1<<P);++s) Spfa(s);
	std::memset(Val,0x3f,sizeof(Val)),
	std::memset(G,0x3f,sizeof(G));
	for(int s=0;s<(1<<P);++s)
		for(int x=1;x<=N;++x) checkMin(Val[s],Dp[x][s]);
	G[0]=0;
	for(int s=1;s<(1<<P);++s)
		for(int t=s;t;t=(t-1)&s)
		{
			int res=0;
			for(int k=0;k<P;++k)
				if(t>>k&1) res|=Freq[Id[k+1]];
			checkMin(G[s],G[s^t]+Val[res]);
		}
	write(G[(1<<P)-1]);
	return 0;
}
/*

*/

另话

对于欧几里得平面上的最小斯坦纳树问题求解拥有比状态压缩更优秀的解法，但好像没有多少人提及，英语比较好，家境比较殷实的人可以看看这个，需要科学上网。

相关文章