题意分析

本题给定带权无向图，每次丢失任意一条边后图仍需保持连通。求使连通性在任意单边失效下不破坏的最小代价子集。

解题思路

本题实质是求加权无向图的最小 2-边连通生成子图，即在图中选取一组边，使得图保持连通且任意一条边失效后仍连通，并且选边的总权重最小。由于 $m\le20, n\le15$，可采用暴力求解：

2-边连通性判定：一个连通图若删除任意一条边仍保持连通，则称其 2-边连通。我们枚举候选边集 $E'$，先验证其连通性，再依次删除每条边，并检查剩余边集是否仍连通，若都连通则 $E'$ 满足条件。

查找速度优化：由于 2-边连通生成子图至少包含 $n$ 条边（比生成树多一条），在遍历 $2^m$ 子集时先跳过边数少于 $n$ 的子集；并可在子集累加过程中与当前最优 $C_{\min}$ 比较，若超出则剪枝。

本题代码

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int u[20], v_[20], w[20];

// 并查集
int parent[16];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}

bool checkSubset(int mask) {
    // 建图并查集
    for (int i = 1; i <= n; ++i) parent[i] = i;
    vector<int> edges;
    for (int i = 0; i < m; ++i) {
        if (mask & (1 << i)) {
            int a = u[i], b = v_[i];
            int pa = findp(a), pb = findp(b);
            if (pa != pb) parent[pa] = pb;
            edges.push_back(i);
        }
    }
    // 首先子集本身需连通
    int root = findp(1);
    for (int i = 2; i <= n; ++i) if (findp(i) != root) return false;
    // 冗余性：删除任一边后仍连通
    for (size_t k = 0; k < edges.size(); ++k) {
        // 重置并查集
        for (int i = 1; i <= n; ++i) parent[i] = i;
        for (size_t j = 0; j < edges.size(); ++j) {
            if (j == k) continue;
            int idx = edges[j];
            int a = u[idx], b = v_[idx];
            int pa = findp(a), pb = findp(b);
            if (pa != pb) parent[pa] = pb;
        }
        int r = findp(1);
        for (int i = 2; i <= n; ++i) if (findp(i) != r) return false;
    }
    return true;
}

int main() {
    int tc = 0;
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        for (int i = 0; i < m; ++i) cin >> u[i] >> v_[i] >> w[i];
        int best = -1;
        int total = 1 << m;
        for (int mask = 0; mask < total; ++mask) {
            // 至少要有 n 边以上
            if (__builtin_popcount(mask) < n - 1) continue;
            if (checkSubset(mask)) {
                int sum = 0;
                for (int i = 0; i < m; ++i) if (mask & (1 << i)) sum += w[i];
                if (best < 0 || sum < best) best = sum;
            }
        }
        if (best < 0) {
            cout << "There is no reliable net possible for test case " << ++tc << ".\n";
        } else {
            cout << "The minimal cost for test case " << ++tc << " is " << best << ".\n";
        }
    }
    return 0;
}
```