ARC078F Mole and Abandoned Mine

题意

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

题解

可以发现最后图的形态一定是一条链，链上可能挂了若干个连通块，要最大化图的边权和。

$n$ 比较小，考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ，加入的点集为 $S$ 时的最大边权和。预处理 $V_s$ 表示集合 $s$ 内部边权之和，$\mathrm{dis}(i,j)$ 表示 $(i,j)$ 边的边权。

每一步可以选一个点 $j$ 加入链，也可以在 $i$ 上挂一个连通块。方程式为：

$$\begin{cases} f(S,i)+\mathrm{dis}(i,j) \rightarrow f(S\cup j,j) \\ f(S,i)+V_{T\cup i}\rightarrow f(S\cup T,i)\end{cases}$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,a,b,c,sum,dis[17][17],v[1<<15],f[1<<15][17];

signed main()
{
    n=read(); m=read();
    const int N=1<<n;
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        sum+=dis[a][b]=dis[b][a]=read();
    }
    for (int i=1;i<N;i++) //预处理 v
    {
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1)) continue;
            for (int k=0;k<j;k++)
            {
                if (!(i>>k&1)) continue;
                v[i]+=dis[j+1][k+1];
            }
        }
    }
    memset(f,-1,sizeof(f));
    f[1][1]=0;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1) || !~f[i][j+1]) continue;
            for (int k=0;k<n;k++) //选一个点 k 加入链
            {
                if (i>>k&1 || !dis[j+1][k+1]) continue;
                f[i|(1<<k)][k+1]=max(f[i|(1<<k)][k+1],f[i][j+1]+dis[j+1][k+1]);
            }
            int tot=((N-1)^i)|(1<<j); //得到可能出现 T∪j 的所有集合
            for (int k=tot;k;k=(k-1)&tot) //枚举子集
            {
                if (!(k>>j&1)) continue;
                f[i|k][j+1]=max(f[i|k][j+1],f[i][j+1]+v[k]); //挂到 j 上
            }
        }
    }
    return !printf("%d\n",sum-f[N-1][n]);
}