[SNOI 2013] Quare

· · 题解

作为一道求包含所有点的最小权边双连通子图的状压 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;
}