题解：P6192 【模板】最小斯坦纳树

~~偶然看到这题还能提交题解来水一发~~

之前 ABC 的 G 题经常出这个啊，但我不会就白搭了吗。

令

dp_{i,|S|}

代表一个包含子集为

|S|

且包含

i

点的最小斯坦纳树。有两种转移，其一是将

dp_{i,|S|}

转移到

dp_{j,|S|}

，代价为

(i,j)

之间的最短路，另一种是

dp_{i,|S|}=dp_{i,|T|}+dp_{i,|S/T|}

，表示将两个子集合并。其中

|S/T|

表示在

S

集中但不在

T

集中的元素。

对每一个新的结果都要跑一遍 dijkstra，我的时间复杂度为

O(nm\log n+3^knk+3^kn\log n)

。

为啥我代码没有火车头都能写得到 2.65K？ZYN 1.08K 结束了。并且他的代码的评测用时之和比我的最慢点还快一倍以上？

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=107;
const int M=5005;
int n,m,k;
int zdl[N][N];
int vis[N][N];
int dp[N][M];	//dp[i][j] 表示整个集合 j 整合在 i 号点上 
int pow2[20],pow3[20];
int point[20];
int point1[N];
vector<pair<int,int> > g[N];
void init(){
	memset(zdl,0x3f,sizeof(zdl));
	memset(point1,-1,sizeof(point1));
	memset(dp,0x3f,sizeof(dp));
	pow2[0]=pow3[0]=1;
	for(int i=1;i<=17;i++){
		pow2[i]=pow2[i-1]*2,pow3[i]=pow3[i-1]*3;
	} 
}  
void dijkstra(int st){
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,st));
	while(!q.empty()){
		int now1=q.top().second,now2=-q.top().first;
		q.pop();
		if(vis[st][now1])	continue;
		vis[st][now1]=1;
		for(int i=0;i<g[now1].size();i++){
			int v=g[now1][i].first,w=g[now1][i].second;
			if(zdl[st][v]>zdl[st][now1]+w){
				zdl[st][v]=zdl[st][now1]+w;
				q.push(make_pair(-zdl[st][v],v));
			}
		}
	}
	if(~point1[st]){
		int bitplace=pow2[point1[st]];
		if(!bitplace)	return;
		for(int i=1;i<=n;i++){
			//这里枚举停留在哪个点 
			dp[i][bitplace]=zdl[st][i]; 
//			cout<<i<<' '<<bitplace<<' '<<dp[i][bitplace]<<endl;
		}
	}
}
int vis1[107];
void dijkstra2(int zt){
	priority_queue<pair<int,int> > q;
	//这里是对 dp[停留位置][zt] 进行转移 
	for(int i=1;i<=n;i++){
		q.push(make_pair(-dp[i][zt],i));
		vis1[i]=0;
	} 
	while(!q.empty()){
		int now1=q.top().second;
		q.pop();
		if(vis1[now1])	continue;
		vis1[now1]=1;
		for(int i=0;i<g[now1].size();i++){
			int v=g[now1][i].first,w=g[now1][i].second;
			if(dp[v][zt]>dp[now1][zt]+w){
				dp[v][zt]=dp[now1][zt]+w;
				q.push(make_pair(-dp[v][zt],v));
			}
		}
	}
}
signed main(){
	init();
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(make_pair(v,w)),g[v].push_back(make_pair(u,w));
	}
	for(int i=0;i<k;i++){
		cin>>point[i],point1[point[i]]=i;
	}//全局中只有 point1 使用 0 开始排序  
	for(int i=1;i<=n;i++){
		zdl[i][i]=0;
		dijkstra(i);
	}
//	cout<<dp[1][1]<<endl;
	for(int i=1;i<pow3[k];i++){
		//三进制状压枚举子集 
		int x1=0,x2=0;	//代表两个子集的具体情况 
		int nowi=i;
		for(int j=0;j<k;j++){
			if(nowi%3==1)	x1+=pow2[j];
			else if(nowi%3==2)	x2+=pow2[j];
			nowi/=3;
			for(int l=1;l<=n;l++){
				dp[l][x1|x2]=min(dp[l][x1|x2],dp[l][x1]+dp[l][x2]);
			}
//			cout<<x1<<' '<<x2<<endl;
		}
		dijkstra2(x1|x2);
//		for(int j=1;j<=n;j++){
//			dp[j][x1|x2]=min(dp[j][x1|x2],dp[j][x1]+dp[j][x2]);
//			cout<<j<<' '<<(x1|x2)<<' '<<dp[j][x1|x2]<<endl;
//		}
	}
	int include13=1e18;
	for(int i=1;i<=n;i++){
		include13=min(include13,dp[i][pow2[k]-1]);
	}
	cout<<include13<<endl;
//	cout<<dp[6][15]<<endl;
	return 0;
}

题解：P6192 【模板】最小斯坦纳树

文章操作

相关推荐

评论

题解：P6192 【模板】最小斯坦纳树