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

problem

ATC-arc078F

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

\(n\le 15, n-1\le m\le \binom n2\)

Solution

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

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

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

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

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

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

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

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

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

Code

#include 

#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