题解：AT_abc364_g [ABC364G] Last Major City

成战犯了，我很晚才把这个题做出来。

没有在板子的基础上有多少加强，但是必须使用优化最短路转移后的最小斯坦纳树算法。（如果你写的是

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

的就过不了，要搞

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

的版本）

因为在

[1,k-1)

区间外只有一个点，最小斯坦纳树的转移又形似

dp_{i,|S|}

，考虑用

i

覆盖

[1,k)

区间以外的点，用

|S|

代表

\left \{ 1,2,3,\dots,k-1 \right \}

的全集。得到所有的答案。

注意本题中的关键点只有

k-1

个。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
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=2*2025,M=2025,mod=1e9+9;	//mod 没有实际意义  
int n,m,k;
vector<pair<int,int> > g[N];

int dp[N][M];	//dp[i][S] 位置为 i 集合为 S 
int pow3[20];
void init(){
	pow3[0]=1;
	for(int i=1;i<=16;i++){
		pow3[i]=pow3[i-1]*3;	//其实这里用不着 mod 了  
	}
} 
int vis[N];
void dijkstra(int S){
	priority_queue<pair<int,int> > q;
	for(int i=1;i<=n;i++){
		q.push(mp(-dp[i][S],i));
		vis[i]=0;
	}
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])	continue;
		vis[u]=1;
//		cout<<'#'<<u<<' '<<dp[u][S]<<endl;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].first,w=g[u][i].second;
			if(dp[v][S]>dp[u][S]+w){
				dp[v][S]=dp[u][S]+w;
				q.push(mp(-dp[v][S],v));
			}
		}
	}
//	cout<<endl;
}
signed main(){
	init();
	for(int i=1;i<=4000;i++){
		for(int j=1;j<=1500;j++){
			dp[i][j]=1e15;
		}
	}
//	memset(dp,0x3f,sizeof(dp)); 
//	cout<<dp[0][0]<<endl; 
//	cout<<dp[0][0]*2<<endl;
//	cout<<dp[0][0]*3<<endl;
//	cout<<dp[0][0]*4<<endl;
//	cout<<dp[0][0]*5<<endl;
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		g[u].push_back(mp(v,w)),g[v].push_back(mp(u,w)); 
	} 
	for(int i=1;i<k;i++){
		dp[i][(1<<i)]=0;	//这些位置代价为 0  
	} 
	for(int i=1;i<pow3[k];i++){
		int now=i,a=0,b=0;	//分解成 a b 两个集合 
		for(int j=0;j<k;j++){
			int x=now%3;
			if(x==1)	a+=(1<<j);
			if(x==2)	b+=(1<<j);
			now/=3; 
		} 
		if(a%2)	continue;	//注意 0 号点不存在 
		if(b%2)	continue;	//同上 
		for(int j=1;j<=n;j++){
			dp[j][a+b]=min(dp[j][a+b],dp[j][a]+dp[j][b]);
		} 
		if(!a){
			dijkstra(a+b);
		}
	}
//	for(int S=1;S<=8;S++){
//		for(int i=1;i<=n;i++){
//			cout<<'#'<<S<<' '<<i<<' '<<dp[i][S]<<endl;
//		}
//	}
	for(int i=k;i<=n;i++){
		write2(dp[i][(1<<k)-2]);
	}
	putchar('\n');
	return 0;
}//痛快一起努力的感觉 我们拥有 同样的机会

题解：AT_abc364_g [ABC364G] Last Major City

文章操作

相关推荐

评论

题解：AT_abc364_g [ABC364G] Last Major City