题解：AT_abc395_g [ABC395G] Minimum Steiner Tree 2

很厉害的题，硬控我一天，让我又补完一场 ABC。

因为是要加入两个点，所以考虑把第一个点放入集合，作为第

k+1

个集合中的点。

接下来就转化成了 ABC364G 的那个问题，考虑

dp_{i,|S|}

代表集合

|S|

与

i

相连通的最小代价，用

|S|

包含点

[1,k]

和自己取的第

k+1

个点。

i

代表第

k+2

个点。

本题 Floyd 转移最短路是没有问题的，建议直接使用 Floyd。

朴素最小斯坦纳树的时间复杂度为

O(3^k(n+k)+2^kn\log n)

，本题因为是 Floyd 转移，并且要枚举第

k+1

个点，所以时间复杂度达到了

O(3^kn^2+2^kn^3)

。不过还是能过的。

CPP

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

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48); 
}
inline void write1(int x){
	write(x),putchar(' '); 
}
inline void write2(int x){
	write(x),putchar('\n');
}
const int N=107;
const int M=2007;
int n,k,q;
int C[N][N];
int dp[N][M][N];	//dp[k+1][S][j] 选取的 k+1 个点为 k+1 集合为 S 目前到了 j  
int key[12];	//注意 key 的最后一位会动态修改 
int pow3[12];
void init(){
	pow3[0]=1;
	for(int i=1;i<=10;i++){
		pow3[i]=pow3[i-1]*3;
	}
} 
signed main(){
	init();
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			C[i][j]=read();
		}
	}
	for(int k_=1;k_<=n;k_++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				C[i][j]=min(C[i][j],C[i][k_]+C[k_][j]);
			}
		}
	}
	for(int i=1;i<=k;i++){
		key[i]=i;
	}
	memset(dp,0x3f,sizeof(dp)); 
	for(int i=1;i<=n;i++){
		dp[i][1<<k][i]=0;
	}
	for(int new_=k+1;new_<=n;new_++){
		//new_ 是第 k+1 个点 
		key[k+1]=new_;
		//然后跑一般的 minimum steiner tree 即可 
		for(int i=1;i<=k+1;i++){
			dp[new_][1<<(i-1)][key[i]]=0;	//代表这个时候先处理为 0 
//			cout<<'#'<<new_<<' '<<(1<<(i-1))<<' '<<key[i]<<' '<<0<<endl; 
		} 
		for(int i=1;i<pow3[k+1];i++){
			int now=i,a=0,b=0;	//分成 a b 两个子集 
			for(int j=0;j<k+1;j++){
				int x=now%3;
				if(x==1)	a+=(1<<j);
				if(x==2)	b+=(1<<j);
				now/=3;
			} 
			for(int j=1;j<=n;j++){
				dp[new_][a|b][j]=min(dp[new_][a|b][j],dp[new_][a][j]+dp[new_][b][j]);
//				cout<<(a|b)<<' '<<new_<<' '<<j<<' '<<dp[new_][a|b][j]<<endl;
			}
			if(a==0){
				for(int j=1;j<=n;j++){
					//转移的都是 dp[new_][a|b][j]
					for(int k_=1;k_<=n;k_++){
						dp[new_][a|b][j]=min(dp[new_][a|b][j],dp[new_][a|b][k_]+C[k_][j]);
//						cout<<(a|b)<<' '<<new_<<' '<<j<<' '<<dp[new_][a|b][j]<<endl;
					} 
				}
			} 
		}
	} 
	q=read();
	while(q--){
		int x=read(),y=read();
		write2(dp[x][(1<<(k+1))-1][y]);
	}
	putchar('\n');
	return 0;
}//天青青等烟雨 而我在等你

其实本题我一直有一种错误思路，就是设

dp_{i,j,|S|}

代表路经

i,j

点且集合为

|S|

的情况。时间复杂度与正确算法相同，请问它错在哪里？

题解：AT_abc395_g [ABC395G] Minimum Steiner Tree 2

文章操作

相关推荐

评论

题解：AT_abc395_g [ABC395G] Minimum Steiner Tree 2