题解-AtCoder ARC-078F Mole and Abandoned Mine

problem

ATC-arc078F

题意概要：给定一个 (n) 点 (m) 边简单无向图（无自环无重边），边有费用，现切去若干条边，使得从 (1) 到 (n) 有且仅有一条简单路径，求最小化花费。

(nle 15,n-1le mle binom n2)

Solution

看到 (nleq 15) 大概就能猜到复杂度是 (O(3^n)) 左右的，然后直接思考用斯坦纳树咋解，无果。

开始思考最终局面的情况，一定是有一条 (1) 到 (n) 的路径，且不能存在其他路径连接这条路径上的两个点。换句话说，就是从每个点出发且只走非路径边的话只能到达一个路径上的点。

考虑原问题要求最小化删边费用，对应上面的做法容易想到要转换为最大化留下来的边权和

把图画出来，大概是说路径上每个点下头都挂上了若干个集合，而由于要最大化比边权和，所以每个集合内部的所有边均予以保留。

那么就很容易得到一个dp：设 (f[i][S]) 表示在路径（最终连接 (1) 和 (n) 的路径）上走到了 (i)，并且集合 (S) 内的点已经挂在了前头，那么有两种转移：

• 在路径上更进一步：(f[i][S] rightarrow f[j][Scup {j}])，增加权值为连接 (i,j) 的边权
• 在当前点挂一个集合：(f[i][S]rightarrow f[i][Scup T])，增加权值为集合 (T) 内所有边的边权和

那么只要预处理一个 (g[S]) 表示集合 (S) 内的边权和，这一步可以暴力求，复杂度 (O(2^nn^2))

再进行转移，转移时需要枚举子集（对于全局而言，枚举补集的子集和枚举子集复杂度相当），复杂度 (O(n3^n))

总复杂度 (O(2^nn^2+n3^n))

Code

#include <cstdio>

#define bin(x) (1<<(x))
#define b(x) (1<<(x)>>1)

inline void cmax(int&x,const int y) {x < y && (x = y);}

const int N = 17,M = 40100;
int f[N][M],g[M];
int mp[N][N];
int n,m;

int main() {
    scanf("%d%d",&n,&m); int Ans = 0;
    for(int i=1,x,y,z;i<=m;++i) {
        scanf("%d%d%d",&x,&y,&z),Ans += z;
        mp[x][y] = mp[y][x] = z;
    }
    for(int s=0;s<bin(n);++s) {
        int&v = g[s];
        for(int i=1;i<=n;++i) if(s & b(i)) 
        for(int j=i+1;j<=n;++j) if(s & b(j)) v += mp[i][j];
    }
    for(int i=1;i<=n;++i)
    for(int j=0;j<bin(n);++j)
        f[i][j] = -1;
    
    f[1][1] = 0;
    for(int S=1;S<bin(n);++S)
    for(int i=1;i<=n;++i) if((S & b(i)) and ~f[i][S]) {
        for(int j=1;j<=n;++j) if((~S & b(j)) and mp[i][j]) cmax(f[j][S|b(j)],f[i][S] + mp[i][j]);
        for(int iS=(bin(n)-1)^S,s = iS; s; s = (s-1) & iS)
            cmax(f[i][S|s],f[i][S] + g[s|b(i)]);
    }
    printf("%dn",Ans - f[n][bin(n)-1]);
    return 0;
}