P6192 【模板】最小斯坦纳树

题目描述：题目

给定一张图上的几个关键点，要求我们用最小的边权将这些点连起来

不难发现，最后连出来的答案一定是一棵树： 如果有环的话，将环优化掉一定更好

我们考虑dp:

对于一个节点x钦定它是这颗树的根。
记 dp[rt][s] 表示以rt为根，关键点被链接的状态为s时的最小花费

则在最短路中有：(对于度为1的节点)

dp[v][s]=min(dp[v][s],dp[u][s]+w[u][v])

对于度不为一的节点：
设ss是s的子集

dp[rt][s]=min(dp[rt][ss],dp[rt][s/ss])

s/ss表示s为全集时ss的补集，在状态压缩中表示为s^ss
剩下细节见代码

时间复杂度不太会分析

code:

#include<bits/stdc++.h>
const int N=105;
const int M=505;
const int inf=1e9;
using namespace std;
int head[N],f[N][1<<10],dl[N],a[N];
int n,m,e_cnt,k;
struct Edge{
	int to,nxt,w;
}e[M<<1];
void add(int x,int y,int w)
{
	e[++e_cnt]={y,head[x],w};
	head[x]=e_cnt;
}
queue<int> Q;
void spfa(int s)
{
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();dl[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to,w=e[i].w;
			if(f[v][s]>f[u][s]+w)
			{
				f[v][s]=f[u][s]+w;
				if(!dl[v])
				{
					Q.push(v);
					dl[v]=1;
				}
			}
		}
	}
}
void init()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			f[i][j]=inf;
		}
	}
}
void work()
{
	init();
	cin>>n>>m>>k;
	for(int i=1,x,y,w;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);add(y,x,w);
	}
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&a[i]);
		f[a[i]][1<<i-1]=0;//自身路径长度为0; 
	}
	int idx=1<<k;idx--;
	for(int s1=0;s1<=idx;s1++)//s1:当前目标点状态 
	{
		for(int i=1;i<=n;i++)//因为这是一棵树,所以考虑以i为根 
		{
			for(int s2=(s1-1)&s1;s2;s2=(s2-1)&s1)//s2:取s1的子集 
			{
				f[i][s1]=min(f[i][s1],f[i][s2]+f[i][s2^s1]);
			}
			if(f[i][s1]!=inf)
			{
				Q.push(i);dl[i]=1;
			} 
		}
		spfa(s1);
	}
	printf("%d",f[a[1]][idx]);
}
int main()
{
	freopen("P6192.in","r",stdin); 
	work();
} 

其实看完之后我自己有个疑问：

则在最短路中有：(对于度为1的节点)
dp[v][s]=min(dp[v][s],dp[u][s]+w[u][v])

在做这个的时候,万一 v 是一个关键点，可是你在做最短路的时候搜到了它，如果它不在s中，我是否应该更新s的状态？

我能想到的解释是：
如果 v 这个点是一个不在s中的关键点而你这样做了，那么这个dp[v][s]大概率会在之后被优化掉

（就好像你买东西只给钱不拿货一样，这种亏本的事情在dp中是不会出现的）

尤其这题还长得这么像爆搜