自动搬运

查看原文

来自洛谷，原作者为

	Captain_Paul 很菜，很划水

搬运于2025-08-24 22:03:36，当前版本为作者最后更新于2018-09-05 19:59:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：给定一个无向图，求把重要节点联通的最小代价（重要节点<=5）

将指定点集合中的所有点连通，且边权总和最小的生成树称为最小斯坦纳树（Minimal Steiner Tree）

其实最小生成树是最小斯坦纳树的一种特殊情况，联通了图上所有节点

最小斯坦纳树可以用dp求解

令$f[i][j]$表示以$i$为根，指定集合中点的联通状态为$j$的最小总权值

转移分为两重

• 第一重：枚举当前状态的子集进行转移

  方程为：$f[i][j]=min(f[i][j],f[i][k]+f[i][j xor k])$

  枚举子集的技巧是：$for (k=j\&(j-1);k;k=j\&(k-1))$

• 第二重：在当前状态下对其进行松弛操作

  方程为:$f[i][j]=min(f[i][j],f[k][j]+cost)$

  在这一重只需对这一种状态进行松弛即可，因为其他状态会通过第一重转移更新

  松弛操作可以通过spfa实现（如果spfa又双叒叕被卡了请使用堆优化dijkstra）

相关题目：[JLOI2015]管道连接 [WC2008]游览计划

现在时限扩大了，加上点常数优化就可以AC了orzzzzz

~虽然我不会写fread~

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
	int to,nxt,dis;
}edge[N<<2];
struct P
{
	int x; ll d;
	inline friend bool operator < (P a,P b) {return a.d>b.d;}
};
int n,m,p,num,head[N];
ll f[N][32],inf,ans=1e18;
bool vis[N];
priority_queue<P>q;
inline int read()
{
	int x=0,w=1;
	char c=getchar();
	while (!isdigit(c)&&c!='-') c=getchar();
	if (c=='-') c=getchar(),w=-1;
	while (isdigit(c))
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*w;
}
inline void add_edge(int from,int to,int dis)
{
	edge[++num]=(node){to,head[from],dis};
	head[from]=num;
}
inline void dijkstra(int S)
{
	memset(vis,0,sizeof(vis));
	while (!q.empty())
	{
		int u=q.top().x; q.pop();
		if (vis[u]) continue; vis[u]=1;
		for (reg int i=head[u];i;i=edge[i].nxt)
		{
			int v=edge[i].to,d=edge[i].dis;
			if (f[v][S]>f[u][S]+d)
			{
				f[v][S]=f[u][S]+d;
				q.push((P){v,f[v][S]});
			}
		}
	}
}
int main()
{
	n=read(),p=read(),m=read();
	memset(f,127/3,sizeof(f)); inf=f[0][0];
	for (reg int i=1;i<=p;i++) f[read()][1<<(i-1)]=0;
	for (reg int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		add_edge(x,y,z); add_edge(y,x,z);
	}
	for (reg int i=1;i<(1<<p);i++)
	{
		for (reg int k=1;k<=n;k++)
		{
		    for (reg int j=i&(i-1);j;j=i&(j-1))
		      f[k][i]=min(f[k][i],f[k][j]+f[k][i^j]);
		    if (f[k][i]<inf) q.push((P){k,f[k][i]});
		}
		dijkstra(i);
	}
	for (reg int i=1;i<=n;i++) ans=min(ans,f[i][(1<<p)-1]);
	printf("%lld\n",ans);
	return 0;
}