AT2657 [ARC078D] Mole and Abandoned Mine 题解

题目链接：AT2657 [ARC078D] Mole and Abandoned Mine

题意：

~~cxy 准备住在一个废弃的矿洞里~~，矿洞的结构可以用一个包含 $n$ 个点，$m$ 条边的连通无向简单图来表示，其中点以 $1,2,\cdots,n$ 编号。第 $i$ 条边连接点 $a_i$ 和 $b_i$，并且移除它需要花费 $c_i$ 元。

cxy 想要移除一些边，使得点 $1$ 和点 $n$ 之间有且仅有唯一的路径，请你帮她寻找满足要求所需的最小花费。

注：一条路径 (path) 指的是不能经过重复点的途径 (walk)，一条迹 (trail) 指的是不能经过重复边的途径。

输入格式：
n m
a1 b1 c1
⋮  ⋮  ⋮
am bm cm
输出格式：

一行，即答案。

数据范围：

保证是连通简单图。

$2 \leq n \leq 15,~n - 1 \leq m \leq \dbinom n2,~1 \leq a_i, b_i \leq n ,~1 \leq c_i \leq 10^6$

它要求 $1$ 到 $n$ 只有 $1$ 条路径，并且不用经过所有点

因此这张图应该长成这样

也就是每个保留路径上的结点都挂着一些结点。

删除的边权值和最小并不是很好处理，可以反过来计算保留的边权值和最大。

注意到 $n\le 15$ ，考虑状压dp

设 $f_{A,u}~(u \in A)$ 表示可以到达的点集为 $A$ ，主路上现在走到 $u$ ，保留的边权值和的最大值。

结合下图，其中蓝色部分表示 $f_{A,u}$ 。

考虑转移。

下文中使用 $a\uparrow b+c$ 表示 $a \leftarrow \max\{a,b+c\}$

第一种，在主路上加入与 $u$ 连通的 $v$ ，也就是图中的红色部分，则

$f_{A\cup \{v\},v} \uparrow f_{A,u} + w(u,v)$

第二种，在 $u$ 下面挂一个连通块，如果把上面的 $v$ 看成 $u$ ，那连通块就是绿色部分，则

$f_{A \cup B,u} \uparrow f_{A,u} + \mathtt{out}(u,B) + \mathtt{in}(B)$

其中，

$\mathtt{out}(u,B)$ 表示 $B$ 中所有与 $u$ 直接相连的点的边权和，即

$\mathtt{out}(u,B)=\sum_{v \in B} w(u,v)$

$\mathtt{in}(B)$ 表示原图 $G$ 的导出子图 $G[B]$ 中所有点的边权和，即

$\mathtt{in}(B) = \dfrac{1}{2} \sum_{u,v\in B} w(u,v)$

$\mathtt{in},\mathtt{out}$ 都是可以在 $O(2^nn^2)$ 的时间内处理出来的

dp转移的复杂度为 $O(3^n n)$

总时间复杂度 $O(2^nn^2 + 3^nn)$ ，看上去后者是瓶颈。

代码：（不明白的话可以参考DP总结-状压dp）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(20))
#define M ((1<<15)+15)
int n,m,res,g[N][N];
int in[M], out[N][M], f[M][N];
void up(int &x,int y) { x < y ? x = y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=0,u,v,w; i<m; i++)
    {
        cin >> u >> v >> w; --u; --v;
        g[u][v] = g[v][u] = w; res+=w;
    }
    int mx = 1 << n;
    // proc in[]
    for(int i=0; i<mx; i++)
        for(int u=0; u<n; u++) if((i >> u) & 1)
            for(int v=u+1; v<n; v++) if((i >> v) & 1)
                in[i] += g[u][v];
    // proc out[][]
    for(int i=0; i<mx; i++)
        for(int u=0; u<n; u++) if(!((i >> u) & 1))
            for(int v=0; v<n; v++) if((i >> v) & 1)
                out[u][i] += g[u][v];
    memset(f,0xc0,sizeof(f));
    f[1][0] = 0;
    for(int i=1; i<mx; i++)
        for(int u=0; u<n; u++)
            if(((i >> u) & 1) && f[i][u] >= 0)
            {
                for(int v=0; v<n; v++)
                    if(!((i >> v) & 1) && g[u][v])
                        up(f[i | (1 << v)][v], f[i][u] + g[u][v]);
                int j = ~ ( ((-1) << n) | i );
                for(; j; j=(j-1) & (~i))
                    up(f[i | j][u], f[i][u] + out[u][j] + in[j]);
            }
    cout << res-f[(1 << n) - 1][n-1] << '\n';
    return 0;
}