[ARC078F] Mole and Abandoned Mine
roger_yrj
·
·
题解
[ARC078F] Mole and Abandoned Mine
前言
看了前两篇题解，一篇时间复杂度不对，一篇排版太乱根本不可读，于是我打算写一篇更好的题解。
题意
### 题解
发现割边很难判断是否只有一条路径，所以尝试将题意转为保留边权和最大的边集。
通过观察发现，最优解一定把这张图分成若干个连通块，然后用一条路径串起来，类似下图：
我们可以 $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\}。
于是总的时间复杂度优化到 $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];
}
```