[ARC078F] Mole and Abandoned Mine

前言

看了前两篇题解，一篇时间复杂度不对，一篇排版太乱根本不可读，于是我打算写一篇更好的题解。

题意

n

个点

m

条边的简单带权无向连通图，要求割掉若干条边，使

1

到

n

只有

1

条路径，问割掉的边权和最小是多少。

题解

发现割边很难判断是否只有一条路径，所以尝试将题意转为保留边权和最大的边集。

通过观察发现，最优解一定把这张图分成若干个连通块，然后用一条路径串起来，类似下图：

我们可以

O(2^nn^2)

预处理出每个连通块的边权和：设

W_S=\sum\limits_{i\in S,j\in S}e_{i,j}

看到

n\le15

，考虑状压 DP。

设

f_{S,i}

表示已经连了

S

中的点，路径走到

i

的最大边权和，考虑如何转移。

我们用刷表法实现转移：

f_{S|T,j}=\max\limits_{T\cap S=\emptyset,j\in T}\left\{f_{S,i}+e_{i,j}+W_T\right\}

时间复杂度

O(3^nn^2+2^nn^2)

，无法通过。（常数小可能过？）

我们可以用一个类似前缀和优化的东西。设

g_{S,j}=\max\limits_{i\in S}\left\{f_{S,i}+e_{i,j}\right\}

，那么原式变为

f_{S|T,j}=\max\limits_{T\cap S=\emptyset,j\in T}\left\{g_{S,j}+W_T\right\}

。

g

可以

O(3^nn)

处理出来，转移优化至

O(3^nn)

。

于是总的时间复杂度优化到

O(3^nn+2^nn^2)

，足以通过本题。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=20,NN=40010;
int n,m,f[NN][N],g[NN][N],W[NN],e[N][N],sum;
int main(){
	cin>>n>>m;
	memset(e,-1,sizeof(e));
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		e[u][v]=e[v][u]=w;
		sum+=w; 
	}
	for(int S=0;S<(1<<n);S++){//预处理连通块 
		for(int i=1;i<=n;i++){
			if(((1<<i)&(S<<1))==0)continue;
			for(int j=i+1;j<=n;j++){
				if(((1<<j)&(S<<1))==0)continue;
				if(~e[i][j])W[S]+=e[i][j];
			}
		}
	}
	memset(f,-0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	for(int S=1;S<(1<<n);S++)if(S&1)f[S][1]=W[S];
	for(int S=1;S<(1<<n);S++){
		for(int i=1;i<=n;i++){//求 g 
			if(((1<<i)&(S<<1))==0)continue;
			for(int j=1;j<=n;j++){
				if((1<<j)&(S<<1))continue;
				if(~e[i][j])g[S][j]=max(g[S][j],f[S][i]+e[i][j]);
			}
		}
		for(int SS=(1<<n)-1-S;SS;SS=(SS-1)&((1<<n)-1-S)){//刷表法求 f 
			for(int j=1;j<=n;j++){
				if(((1<<j)&(SS<<1))==0)continue;
				if(!S&&j!=1)continue;
				f[S|SS][j]=max(f[S|SS][j],g[S][j]+W[SS]);
			}
		}
	}
	cout<<sum-f[(1<<n)-1][n];
}

[ARC078F] Mole and Abandoned Mine

文章操作

[ARC078F] Mole and Abandoned Mine

前言

题意

题解

代码

相关推荐

评论

[ARC078F] Mole and Abandoned Mine