[DP记录]AT2657 [ARC078D] Mole and Abandoned Mine
command_block
2021-05-13 16:43:23
**题意** ： 给一个 $n$ 个点 $m$ 条边的无向连通简单图，边有边权。
要求割掉若干条边，使 $1$ 到 $n$ 只有一条简单路径，问割掉的边权和最小是多少。
$n\leq 15$ ，时限$\texttt{4s}$。
------------
取反后可以转化为 ： 保留一个边集使 $1$ 到 $n$ 只有一条简单路径，且边权和最大。
观察符合题意的图会长什么样，如下图 ：
会有很多子图挂在 $1\leftrightarrow n$ 的那条唯一的简单路径上，挂在两个不同点上的子图不能连通（如图中蓝边），否则不合法。
考虑状压 $\rm DP$ ，每次向链上加入一个点以及其挂着的子图。
记 $dp[S,t]$ 表示已经考虑了集合 $S$ 内的点，链的末尾为 $t$ 的最优解。
记 $w(u,v)$ 为 $u,v$ 之间的边权（若边不存在则为 $-\infty$ ）， $W(S)$ 为集合 $S$ 内部的边权和。
则有转移 ：
$$dp[S+\{u\},u]\leftarrow dp[S,t]+w(t,u)\quad(u\notin S)$$
$$dp[S+T,t]\leftarrow dp[S,t]+W(T+\{t\})\quad(S∩T=\varnothing)$$
分别对应 “将链延长” 与 “挂一个子图在当前端点上”。
复杂度 $O(3^nn)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 16
#define MaxS 33000
using namespace std;
const int INF=1000000000;
int n,m,w[MaxS],h[MaxN][MaxN],dp[MaxS][MaxN];
int main()
{
scanf("%d%d",&n,&m);
int ans=0;
for (int i=1,u,v,c;i<=m;i++){
scanf("%d%d%d",&u,&v,&c);
u--;v--;h[u][v]=h[v][u]=c;
ans+=c;
}
for (int s=1;s<(1<<n);s++)
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if ((s>>i&1)&&(s>>j&1))
w[s]+=h[i][j];
for (int s=1;s<(1<<n);s++)
for (int i=0;i<n;i++)dp[s][i]=-INF;
dp[1][0]=0;
for (int s=1;s<(1<<n);s+=2)
for (int i=0;i<n;i++)if ((s>>i&1)&&dp[s][i]>=0){
for (int j=0;j<n;j++)if (!(s>>j&1)&&h[i][j])
dp[s|(1<<j)][j]=max(dp[s|(1<<j)][j],dp[s][i]+h[i][j]);
int s2=((1<<n)-1)^s;
for (int t=s2;t;t=(t-1)&s2)
dp[s|t][i]=max(dp[s|t][i],dp[s][i]+w[t|(1<<i)]);
}
printf("%d",ans-dp[(1<<n)-1][n-1]);
return 0;
}
```