自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:14:17，当前版本为作者最后更新于2021-12-16 16:42:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为一道求包含所有点的最小权边双连通子图的状压 DP 题，做法与其强连通分量版本 https://codeforces.ml/gym/102759/problem/C 是近乎一样的。

首先我们需要了解 耳分解。

这里这样定义耳（不知道是否标准）：对于（强）连通图 $G$，耳是一条路径 $a_1\to \ldots\to a_m$，满足 $a_1,\ldots,a_{m-1}$ 两两不同且 $a_2,\ldots,a_m$ 两两不同（也就是说是一条简单路径或简单圈），并且 $a_2,\ldots,a_{m-1}$ 的度数都为 $2$，并且删除这上面所有边后不影响 $a_2,\ldots,a_{m-1}$ 以外点的（强）连通性。

定义一张图是可耳分解的，当且仅当可以每次从中删去一个耳，并且最终所有边都被删除。

我们有如下定理：

一张有向图是可耳分解的，当且仅当它强连通。

一张无向图是可耳分解的，当且仅当它边双联通。

上一条定理是用来做那道 open cup 题的，而下一条则是做本题的。

于是我们有一个 naive 算法，倒做耳分解，往一个空图中不断加耳。

令 $f(S)$ 表示包含集合 $S$ 中所有点的最小权双连通分量，枚举与 $S$ 不交的点集 $T$，将 $T$ 连成耳后两端与 $S$ 中的某两个点连接即可，时间复杂度为 $O(3^n\times \operatorname{poly}(n))$。

但是 naive 算法还是 naive 算法，就算能过这题也过不了那个有向图版本，我们进行一个优化。

上面将耳看做了一个整体，但我们不妨将耳逐步加入，具体地，令 $f(S,i,j)$ 表示当前考虑了 $S$ 中的点，但是 $S$ 中最后加入的一个耳还是不完整的，耳伸出去部分的一个端点是 $i$，最终需要与 $j$ 连接上，此时已经加入的所有边的最小权值和。

那么转移只要每次枚举耳上 $i$ 的后继即可。

时间复杂度为 $O(2^n\times \operatorname{poly}(n))$，注意实现细节。

目前这份代码是本题最优解。

#include <bits/stdc++.h>
using namespace std;
int t,n,m,x,y,z,d[20][20][2],dp[1<<12][14][14][2],f[1<<12];
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		memset(d,0x2f,sizeof(d));
		memset(dp,0x2f,sizeof(dp));
		memset(f,0x2f,sizeof(f));
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++) {
			scanf("%d%d%d",&x,&y,&z);
			x--,y--;
			if (z<d[x][y][0]) {d[x][y][1]=d[x][y][0],d[x][y][0]=z;}
			else if (z<d[x][y][1]) {d[x][y][1]=z;}
			swap(x,y);
			if (z<d[x][y][0]) {d[x][y][1]=d[x][y][0],d[x][y][0]=z;}
			else if (z<d[x][y][1]) {d[x][y][1]=z;}
		}
		for (int i=0;i<n;i++) {f[1<<i]=0;}
		for (int i=1;i<(1<<n);i++) {
			for (int j=0;j<n;j++) {
				if (!(i&(1<<j))) {continue;}
				for (int k=0;k<n;k++) {
					if (!(i&(1<<k))) {continue;}
					f[i]=min(f[i],dp[i][j][k][1]+d[j][k][0]);
				}
			}
			if (f[i]<0x2f2f2f2f) {
				for (int j=0;j<n;j++) {
					if (i&(1<<j)) {continue;}
					for (int k=0;k<n;k++) {
						if (!(i&(1<<k))) {continue;}
						f[i|(1<<j)]=min(f[i|(1<<j)],f[i]+d[j][k][0]+d[j][k][1]);
					}
				}
				for (int j=0;j<n;j++) {
					if (!(i&(1<<j))) {continue;}
					for (int k=0;k<n;k++) {
						if (!(i&(1<<k))) {continue;}
						for (int l=0;l<n;l++) {
							if (i&(1<<l)) {continue;}
							dp[i|(1<<l)][l][k][0]=min(dp[i|(1<<l)][l][k][0],f[i]+d[j][l][0]);
							if (j!=k) {f[i|(1<<l)]=min(f[i|(1<<l)],f[i]+d[j][l][0]+d[k][l][0]);}
						}
					}
				}
			}
			for (int j=0;j<n;j++) {
				if (!(i&(1<<j))) {continue;}
				for (int k=0;k<n;k++) {
					if (!(i&(1<<k))) {continue;}
					if (min(dp[i][j][k][0],dp[i][j][k][1])==0x2f2f2f2f) {continue;}
					for (int l=0;l<n;l++) {
						if (i&(1<<l)) {continue;}
						dp[i|(1<<l)][l][k][1]=min(dp[i|(1<<l)][l][k][1],
						min(dp[i][j][k][0],dp[i][j][k][1])+d[j][l][0]);
					}
				}
			}
		}
		if (f[(1<<n)-1]==0x2f2f2f2f) {printf("impossible\n");}
		else {printf("%d\n",f[(1<<n)-1]);}
	}
	return 0;
}