本文主要是介绍#斯坦纳树，状压dp#洛谷 3264 [JLOI2015]管道连接，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

分析

如果对于每一个频道单独跑斯坦纳树可能会存在两种频道共用一条道路而重复统计的情况，
考虑状压dp，设\(f[s]\)表示选择频道二进制状态为\(s\)的最小贡献，那么对于每个状态跑斯坦纳树然后状压求最小值即可

代码

#include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#include <cstring>
#define rr register
using namespace std;
const int N=1101; vector<int>K[11];
struct node{int y,w,next;}e[N*6]; queue<int>q;
int dp[N][N],f[N],as[N],two[11],n,m,kk,k,v[N],et=1,a[11],b[11];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
inline void Spfa(int z){
	while (!q.empty()){
		rr int x=q.front(); q.pop();
		for (rr int i=as[x];i;i=e[i].next)
		if (dp[z][e[i].y]>dp[z][x]+e[i].w){
			dp[z][e[i].y]=dp[z][x]+e[i].w;
			if (!v[e[i].y]) v[e[i].y]=1,q.push(e[i].y);
		}
		v[x]=0;
	}
}
inline void Steiner(int o){
	for (rr int S=1;S<two[o];++S){
		for (rr int i=1;i<=n;++i){
		    for (rr int j=S&(S-1);j;j=(j-1)&S)
		    if (dp[S][i]>dp[j][i]+dp[S^j][i])
		    	dp[S][i]=dp[j][i]+dp[S^j][i];
		    if (dp[S][i]<0x3f3f3f3f) q.push(i),v[i]=1;
		}
		Spfa(S);
	}	
}
signed main(){
	n=iut(),m=iut(),kk=iut(),two[0]=1;
	for (rr int i=1;i<=m;++i){
		rr int x=iut(),y=iut(),w=iut();
		e[++et]=(node){y,w,as[x]},as[x]=et;
		e[++et]=(node){x,w,as[y]},as[y]=et;
	}
	memset(v,-1,sizeof(v));
	for (rr int i=1;i<=kk;++i){
		a[i]=iut(),b[i]=iut();
		if (v[a[i]]==-1) v[a[i]]=k++;
		K[v[a[i]]].push_back(b[i]);
	}
	for (rr int i=1;i<=kk;++i) two[i]=two[i-1]<<1;
	f[0]=0,memset(v,0,sizeof(v));
	for (rr int S=1;S<two[k];++S){
		memset(dp,0x3f,sizeof(dp));
		rr int now,len,o=0;
		for (rr int j=0;j<k;++j)
		if ((S>>j)&1){
			len=K[j].size(),now=K[j][0];
			for (rr int i=0;i<len;++i)
			    dp[two[o++]][K[j][i]]=0;
		}
		Steiner(o);
		f[S]=dp[two[o]-1][now];
	}
	for (rr int S=1;S<two[k];++S)
	for (rr int j=S&(S-1);j;j=(j-1)&S)
	    if (f[S]>f[j]+f[S^j]) f[S]=f[j]+f[S^j];
	return !printf("%d",f[two[k]-1]);
}

这篇关于#斯坦纳树，状压dp#洛谷 3264 [JLOI2015]管道连接的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！