题目地址：BZOJ：Problem 3590. — [Snoi2013]Quare

题目描述

4.20四川芦山地震发生后，抗震救灾委员会接到一个紧急任务，四川省给该委员会发了一份地图，这份地图给出了该省一些城市的情况：任两个城市是用一条或多条公路连接起来的，也可以没有公路连接，但是每个城市都可以直接或间接地到达另外的城市，注意这些公路是可以双向行驶的。由于最近余震、暴雨造成泥石流倾泻，使得车辆在这些公路上行驶很不安全，于是四川省决定尽快对部分公路进行抢修，以保障救援车辆行车安全。
该省对所有的公路情况都进行了勘察，分析估计了抢修某段公路所需要花费的时间，并记录在地图中。现在该省希望抗震救灾委员会能找到一个方案，该方案决定出哪些公路需要抢修，使得抢修后的公路仍能保证任意两个城市之间都能直接或间接地相连，同时为了安全起见，即使某一条抢修的公路被泥石流阻断了，任意两城市仍能保持这个性质。由于时间紧迫，抗震救灾委员会还需保证找到的这个方案总抢修时间最短。

题意简述

给你一个连通无向图，求这个图的一个包含所有点的最小权边双连通子图。

输入输出格式

输入格式：
输入文件有多组数据，第1行为 1 个整数t，为 case总数，接下来按顺序给出每个case 描述，首先是两个整数 n，m（1≤n≤12, 1≤m≤40）分别表示城市数量和公路数量，下面m行每行 3个整数x，y，c 描述了一条公路的情况：x城市与y城市之间的一条公路，抢修该公路需要 c个单位时间。
注意上面所说的两城市间可能有多条公路。

输出格式：
按顺序输出每个 case 的结果，如果找不到一条合适的方案，则输出一行“impossible”，否则输出一个整数，为抢修的最优方案所需要的总时间。

输入输出样例

输入样例#1：

2
4 6
1 2 1
1 3 2
1 3 3
2 4 2
3 4 1
2 3 1
2 1
1 2 3

输出样例#1：

6
impossible

题解

参考资料：BZOJ3590【状压DP】 – CSDN博客
看到了数据范围就想到状压，但是DP并不好做。
我们想到一个边双连通分量可以从一个小的子分量加上一条链扩展而来，即把这条链通过端点的出边连接到子分量上。
我们考虑处理出$g[S][u][v]$表示状态$S$中的所有点构成一条链，端点分别是$u$和$v$的最小权值和。显然只有一个点的链权值为0，只有一条边的链权值为边权，这些可以作为DP初值。然后枚举$u$、$v$和一条$v$的出边，把出边连接的点并入链中这样转移就好。
还要处理出$h[S][u][0/1]$表示$u$到状态$S$（$u \notin S$）中的任意一点的最短距离和次短距离。对于每一个$S$，枚举一个不在里面的点$u$然后枚举出边求最小值即可。
有了上面的信息，我们可以开始计算答案了，$f[S]$表示$S$内的点构成一个点双连通分量的最小权值和。我们每次往$S$中加入一条链，如果这条链是一个点，那么要加上这个点到$S$的最短和次短距离，否则加上链两个端点到$S$的最短距离和链权和。
也就是说，这个题本身是一个大力DP题。复杂度比较难看。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int INF = 0x10101010;

int T, n, m;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[15];

int bin[15], cnt[1 << 12], f[1 << 12], g[1 << 12][15][15], h[1 << 12][15][2];

int main() {
    T = readint();
    for(int i = 1; i < 15; i++) bin[i] = 1 << (i - 1);
    for(int i = 1; i < (1 << 12); i++) cnt[i] = cnt[i >> 1] + (i & 1);
    while(T--) {
        n = readint(); m = readint();
        for(int i = 1; i <= n; i++) gra[i].clear();
        for(int i = 1, u, v, w; i <= m; i++) {
            u = readint(); v = readint(); w = readint();
            gra[u].push_back(Edge {v, w});
            gra[v].push_back(Edge {u, w});
        }
        memset(g, 0x10, sizeof(g));
        for(int i = 1; i <= n; i++) {
            g[bin[i]][i][i] = 0;
        }
        for(int u = 1; u <= n; u++) {
            for(int i = 0; i < gra[u].size(); i++) {
                int v = gra[u][i].to;
                g[bin[u] | bin[v]][u][v] = std::min(g[bin[u] | bin[v]][u][v], gra[u][i].w);
            }
        }
        for(int i = 1; i < (1 << n); i++) {
            for(int u = 1; u <= n; u++) {
                for(int v = 1; v <= n; v++) {
                    if(!(i & bin[u]) || !(i & bin[v])) continue;
                    for(int j = 0; j < gra[v].size(); j++) {
                        int w = gra[v][j].to;
                        if(i & bin[w]) continue;
                        g[i | bin[w]][u][w] =
                            std::min(g[i | bin[w]][u][w], g[i][u][v] + gra[v][j].w);
                    }
                }
            }
        }
        memset(h, 0x10, sizeof(h));
        for(int i = 1; i < (1 << n); i++) {
            for(int u = 1; u <= n; u++) {
                if(i & bin[u]) continue;
                for(int j = 0; j < gra[u].size(); j++) {
                    int v = gra[u][j].to;
                    if(!(i & bin[v])) continue;
                    if(gra[u][j].w <= h[i][u][0]) {
                        h[i][u][1] = h[i][u][0];
                        h[i][u][0] = gra[u][j].w;
                    } else if(gra[u][j].w < h[i][u][1]) {
                        h[i][u][1] = gra[u][j].w;
                    }
                }
            }
        }
        memset(f, 0x10, sizeof(f));
        for(int i = 1; i <= n; i++) {
            f[bin[i]] = 0;
        }
        for(int i = 1; i < (1 << n); i++) {
            if(cnt[i] < 2) continue;
            for(int s = (i - 1) & i; s; s = (s - 1) & i) {
                int t = i - s;
                for(int u = 1; u <= n; u++) {
                    for(int v = 1; v <= n; v++) {
                        if((s & bin[u]) && (s & bin[v])) {
                            if(u == v) {
                                f[i] = std::min(f[i], f[t] + g[s][u][u] + h[t][u][0] + h[t][u][1]);
                            } else {
                                f[i] = std::min(f[i], f[t] + g[s][u][v] + h[t][u][0] + h[t][v][0]);
                            }
                        }
                    }
                }
            }
        }
        if(f[(1 << n) - 1] >= INF) {
            puts("impossible");
        } else {
            printf("%d\n", f[(1 << n) - 1]);
        }
    }
    return 0;
}