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;
}