转载注明来源:https://www.cnblogs.com/syc233/p/13650130.html


姑且当作状压DP的复习了。


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

用一道模板题来引入问题:

P6192 【模板】最小斯坦纳树

给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)

再给定包含 \(k\) 个结点的点集 \(S\),选出 \(G\) 的子图 \(G′=(V′,E′)\),使得:

  1. \(S\subseteq V'\)
  2. \(G'\) 为连通图;
  3. \(E'\) 中所有边的权值和最小。

\(E'\) 中所有边的权值和。

为了使边权和最小, \(G'\) 一定是一棵树,证明类比最小生成树。

考虑状压DP,令 \(f(i,s)\) 表示以 \(i\) 为根的包含点集 \(s \subseteq S\) 的树的最小边权和。则有转移:

  • \(i\) 的度数为 \(1\) ,则枚举与它有边相连的点转移, \(f(i,s)=\min_{j}f(j,s)+w(i,j)\)
  • \(i\) 的度数大于 \(1\) ,则划分成几个子树求解, \(f(i,s)=\min_{t \subseteq s}f(i,t)+f(i,s-t)\)

第一种转移可以每次跑最短路实现。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#define maxn 105
#define maxm 505
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

struct edge
{
	int u,v,w,next;
}e[maxm<<1];

int head[maxn],k;

inline void add(int u,int v,int w)
{
	e[k]=(edge){u,v,w,head[u]};
	head[u]=k++;
}

int n,m,K;
int f[maxn][1<<11];
bool vis[maxn];

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;

inline void Dijkstra(int S)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(f[v][S]>f[u][S]+e[i].w)
			{
				f[v][S]=f[u][S]+e[i].w;
				q.push(make_pair(f[v][S],v));
			}
		}
	}
}

int p[11];

int main()
{
	// freopen("P6192.in","r",stdin);
	read(n),read(m),read(K);
	memset(head,-1,sizeof(head));
	for(int i=1,u,v,w;i<=m;++i)
	{
		read(u),read(v),read(w);
		add(u,v,w);add(v,u,w);
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=K;++i)
	{
		read(p[i]);
		f[p[i]][1<<(i-1)]=0;
	}
	for(int S=1;S<(1<<K);++S)
	{
		for(int i=1;i<=n;++i)
		{
			for(int S0=S&(S-1);S0;S0=(S0-1)&S&(S-1))
				f[i][S]=min(f[i][S],f[i][S0]+f[i][S^S0]);
			if(f[i][S]!=INF) q.push(make_pair(f[i][S],i));
		}
		Dijkstra(S);
	}
	printf("%d\n",f[p[1]][(1<<K)-1]);
	return 0;
}

练习

P4294 [WC2008]游览计划

棋盘图上求解最小斯坦纳树。由于这道题是点权,所以转移方程有所不同:

\[\begin{aligned} &f(i,s)=\min f(j,s)+a_i\\ &f(i,s)=\min_{t \subseteq s} f(i,t)+f(i,s-t)-a_i \end{aligned} \]

另外这题需要输出方案,所以对每一个状态都要记录前驱,略恶心。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#define maxn 105
#define maxm 2005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

struct edge
{
	int u,v,next;
}e[maxm<<1];

int head[maxn],k;

inline void add(int u,int v)
{
	e[k]=(edge){u,v,head[u]};
	head[u]=k++;
}

typedef pair<int,int> pii;
pii pre[maxn][1<<11];
int n,m,K,a[maxn],p[maxn];
int f[maxn][1<<11];
bool vis[maxn];

priority_queue<pii,vector<pii>,greater<pii> > q;

inline void Dijkstra(int S)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(f[v][S]>f[u][S]+a[v])
			{
				f[v][S]=f[u][S]+a[v];
				pre[v][S]=make_pair(u,S);
				q.push(make_pair(f[v][S],v));
			}
		}
	}
}

inline int pos(int x,int y) {return (x-1)*m+y;}

int ans[15][15];

inline void dfs(int u,int S)
{
	if(!pre[u][S].second) return;
	ans[(u-1)/m+1][(u-1)%m+1]=1;
	if(pre[u][S].first==u) dfs(u,S^pre[u][S].second);
	dfs(pre[u][S].first,pre[u][S].second);
}

int main()
{
	// freopen("P4294.in","r",stdin);
	read(n),read(m);
	memset(head,-1,sizeof(head));
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int u=pos(i,j);
			read(a[u]);
			if(!a[u])
			{
				p[++K]=u;
				f[p[K]][1<<(K-1)]=0;
			}
			if(i-1>=1)
			{
				add(u,pos(i-1,j));
				add(pos(i-1,j),u);
			}
			if(j-1>=1)
			{
				add(u,pos(i,j-1));
				add(pos(i,j-1),u);
			}
		}
	for(int S=1;S<(1<<K);++S)
	{
		for(int i=1;i<=n*m;++i)
		{
			for(int S0=S&(S-1);S0;S0=(S0-1)&S&(S-1))
				if(f[i][S]>f[i][S0]+f[i][S^S0]-a[i])
				{
					f[i][S]=f[i][S0]+f[i][S^S0]-a[i];
					pre[i][S]=make_pair(i,S0);
				}
			if(f[i][S]!=INF) q.push(make_pair(f[i][S],i));
		}
		Dijkstra(S);
	}
	printf("%d\n",f[p[1]][(1<<K)-1]);
	dfs(p[1],(1<<K)-1);
	for(int i=1;i<=n;++i,puts(""))
		for(int j=1;j<=m;++j)
		{
			int u=pos(i,j);
			if(!a[u]) putchar('x');
			else if(ans[i][j]) putchar('o');
			else putchar('_');
		}
	return 0;
}

P3264 [JLOI2015]管道连接

不同的是这道题的关键点分为几类,求的是使得任意同类关键点都连通的最小花费。

先求一遍最小斯坦纳树,得到 \(f\) 数组。

\(g(s)\) 表示令点类 \(s\) 连通的最小花费, \(cnl_i\) 表示类别为 \(i\) 的点集。则有转移:

  • 直接让点类 \(s\) 中的每一类的所有点都连通,则 \(g(s)=\min_{i=1}^n f(i,\bigcup_{k \in s}cnl_k)\)
  • \(s\) 分裂成两个集合,则 \(g(s)=\min_{t \subseteq s}g(t)+g(s-t)\)

这道题不知道为什么用Dijkstra会比SPFA慢。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn 1005
#define maxm 3005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

struct edge
{
	int u,v,w,next;
}e[maxm<<1];

int head[maxn],k;

inline void add(int u,int v,int w)
{
	e[k]=(edge){u,v,w,head[u]};
	head[u]=k++;
}

int n,m,K,p[11];
int f[maxn][1<<11],g[1<<11],cnl[11];
bool vis[maxn];

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;

inline void Dijkstra(int S)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(f[v][S]>f[u][S]+e[i].w)
			{
				f[v][S]=f[u][S]+e[i].w;
				q.push(make_pair(f[v][S],v));
			}
		}
	}
}

int main()
{
	// freopen("P3264.in","r",stdin);
	read(n),read(m),read(K);
	memset(head,-1,sizeof(head));
	for(int i=1,u,v,w;i<=m;++i)
	{
		read(u),read(v),read(w);
		add(u,v,w);
		add(v,u,w);
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1,c;i<=K;++i)
	{
		read(c);read(p[i]);
		f[p[i]][1<<(i-1)]=0;
		cnl[c]|=1<<(i-1);
	}
	for(int S=1;S<(1<<K);++S)
	{
		for(int i=1;i<=n;++i)
		{
			for(int S0=(S-1)&S;S0;S0=(S0-1)&(S-1)&S)
				f[i][S]=min(f[i][S],f[i][S0]+f[i][S^S0]);
			if(f[i][S]!=INF) q.push(make_pair(f[i][S],i));
		}
		Dijkstra(S);
	}
	memset(g,0x3f,sizeof(g));
	g[0]=0;
	for(int S=1;S<(1<<K);++S)
	{
		int S1=0;
		for(int i=0;i<K;++i)
			if((S>>i)&1) S1|=cnl[i+1];
		for(int i=1;i<=n;++i)
			g[S]=min(g[S],f[i][S1]);
		for(int S0=(S-1)&S;S0;S0=(S0-1)&(S-1)&S)
			g[S]=min(g[S],g[S0]+g[S^S0]);
	}
	printf("%d\n",g[(1<<K)-1]);
	return 0;
}