『图论·状态压缩DP』AT2657：Mole and Abandoned Mine

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

给一个n个点m条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使1到n只有1条路径（不经过重复点），问割掉的边权和最小是多少。

$\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

很显然根据数据规模我们可以确定是状态压缩，我们考虑如何转移。

状态很简单，用 $f[s][i]$ 表示点即为 $s$ ，且 $1$ 号点最终停留到 $j$ 号点，且 $i$ 到 $j$ 路径只有一条的最大保留数。

状态的转移分成两种：

• 当前转台转移到新的点：$$f[i][j]+v(j,k)\to f[i\cup k][k]$$
• 当两个联通块合并且以当前状态为终点时：$$f[i][j]+S[k]\to f[i\cup k][j]$$
  $S$表示保留点集为$S$的所有边的边权和。

接下来考虑如何求解$S$，显然我们可以采用递推的方法.比如当前状态为$S$，可以枚举$j$，用S更新$S\cup j$。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>using namespace std;
const int N = 20;int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' or c > '9') w |= c == '-', c = getchar();while (c >= '0' and c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int n, m, sum = 0;
int f[1<<N][N], S[1<<N], val[N][N], in[1<<N];vector <int> a[N];int main(void)
{
    n = read(), m = read();memset(f,-1,sizeof f);for (int i=1,x,y,v;i<=m;++i){
    x = read()-1, y = read()-1, v = read();val[x][y] = val[y][x] = v;sum += v;a[x].push_back(y);a[y].push_back(x);}for (int i=0;i<1<<n;++i)for (int j=0;j<n;++j)if (((i>>j) & 1) == 0 and in[i|(1<<j)] == 0) {
    int cnt = S[i];for (int k=0;k<a[j].size();++k)if ((i >> a[j][k]) & 1) cnt += val[j][a[j][k]];S[i|(1<<j)] = cnt;}f[1][0] = 0;for (int i=0;i<1<<n;++i)for (int j=0;j<n;++j) if (((i >> j) & 1) and f[i][j] != -1){
    if (f[i][j] == -1) continue;for (int k=0;k<n;++k) if (((i >> k) & 1) == 0 && val[j][k]) f[i|(1<<k)][k] = max(f[i|(1<<k)][k],f[i][j]+val[j][k]);int t = (1<<j) | (((1<<n)-1)^i);for (int k=t;k;k=(k-1)&t) if ((k >> j) & 1) f[i|k][j] = max(f[i|k][j],f[i][j]+S[k]);}  cout<<(sum - f[(1<<n)-1][n-1]);return 0;
}