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

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

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

输入格式

\begin{array}l 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 \end{array}

输出格式

题解

直接考虑移除边的最小花费不好处理，可以反过来，考虑保留尽可能多的边，使得保留的边的总权值和最大。

由于点 $1$ 到点 $n$ 之间有唯一的路径，可以得到，最终保留的边应该为一条 $1$ 到 $n$ 的路径 (记作主路)，还有路径上每个点挂着一个连通块，如下图所示。

记 $f_{A, u}$ ($u \in A$) 表示当前可到达集合 $A$ 中的点，主路上到达的最远的点是 $u$，保留的边的权值和的最大值 (结合上图，就是蓝色部分权值和的最大可能值)。

考虑转移，第一种情况，就是加入与 $u$ 连通的点 $v$，结合上图，就是加入浅蓝色部分，则有转移

其中 $G_{u, v}$ 表示连接 $u$ 和 $v$ 的边的权值，$a \uparrow b$ 代表 a = max(a, b)。

第二种情况，就是点 $u$ 不变，而在下面挂一个连通块，结合上图，就是加入浅红色部分 $B$，则有转移

其中 $in(A)$ 代表 $G$ 的导出子图 $G[A]$ 中所有点的边权和，即 $\dfrac 12 \sum\limits_{u, v \in A} G_{u, v}$，$out(v, A)$ 代表 $A$ 中所有与 $v$ 相连的点与 $v$ 的边的权值和，即 $\sum\limits_{u \in A} G_{u, v}$。

那么最终答案就是 $in(V) - f_{V, n}$，其中 $V$ 是总点集。当然，在实现的时候，集合用一个二进制数来表示就可以了。

显然 $G, in, out$ 是可以在 $O(2^n n^2)$ 的时间内预处理出来的，又由子集的性质，两个转移时间复杂度分别是 $O(2^n n^2)$ 和 $O(3^n n)$，故总时间复杂度为 $O(3^n n)$。

代码

#include <bits/stdc++.h>
#define N 20
#define N2 65634
using namespace std;

int V, E;
int i, u, v, w;
int G[N][N];
int f[N2][N];
int in[N2], out[N][N2], ans;

void up(int &x, const int y) {x < y ? x = y : 0;}

int main(){
    scanf("%d%d", &V, &E);
    for(i = 0; i < E; ++i){
        scanf("%d%d%d", &u, &v, &w); --u; --v;
        G[u][v] = G[v][u] = w; ans += w;
    }
    for(i = 0; i < 1 << V; ++i)
        for(u = 0; u < V; ++u) if(i >> u & 1)
            for(v = u + 1; v < V; ++v) if(i >> v & 1)
                in[i] += G[u][v];
    for(i = 0; i < 1 << V; ++i)
        for(u = 0; u < V; ++u) if(!(i >> u & 1))
            for(v = 0; v < V; ++v) if(i >> v & 1)
                out[u][i] += G[u][v];
    memset(f, 128, sizeof f);
    f[1][0] = 0;
    for(i = 1; i < 1 << V; ++i)
        for(u = 0; u < V; ++u) if((i >> u & 1) && f[i][u] >= 0){
            for(v = 0; v < V; ++v) if(!(i >> v & 1) && G[u][v])
                up(f[i | 1 << v][v], f[i][u] + G[u][v]);
            v = ~(-1 << V | i);
            for(; v; v = v - 1 & ~i)
                up(f[i | v][u], f[i][u] + out[u][v] + in[v]);
        }
    printf("%d\n", ans -= f[(1 << V) - 1][V - 1]);
    return 0;
}

坑

这题注意枚举子集的时候不要两个都 for 到 $2^n$，不然时间可能会退化到 $O(4^n n)$，约有 $1.6 \times 10^{10}$，很可能要 TLE 掉，因此这里有一个~~流传已久~~的算法，以枚举 $A$ 的非空子集为例：

// A is a set
for(i = A; i; i = i - 1 & A)
    // do something

这样，变量 $i$ 就可以遍历 $A$ 的所有非空子集，这样总时间复杂度就可以降到 $O(3^n n)$。

坑1：注意计算 in[] 的时候，枚举 $u, v$ 时同一对 $\{u, v\}$ 不能重复，因此，可以加限制条件 $u < v$，或者最终结果除以 $2$ 均可。

题目描述

输入格式

输出格式

题解

代码

坑