就是求桥而已,但是坑点很多。求出权值最小的桥,然后输出其权值。但是如果权值为零,我们仍要派一名士兵。
另外如果图本身就不连通,我们优先输出0

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
const int max_m = 1e6 + 100;
const int max_n = 1e3 + 100;
struct edge {
    int to, rev, next, cost;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cost,int rev) {
    E[cnt].to = to;E[cnt].rev = rev;
    E[cnt].cost = cost;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
int dfn[max_n], low[max_n];
int tot = 0;
bool is[max_m];
void tarjan(int u, int fa_id) {
    dfn[u] = low[u] = ++tot;
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (i == fa_id)continue;
        if (!dfn[v]) {
            tarjan(v, E[i].rev);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                is[i] = is[E[i].rev] = true;
        }
        else low[u] = min(low[u], dfn[v]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)break;
        fill(head, head + max_n, 0);cnt = 1;
        fill(dfn, dfn + max_n, 0);
        fill(is, is + max_m, 0);tot = 0;
        for (int i = 1, u, v, c;i <= m;++i) {
            cin >> u >> v >> c;
            add(u, v, c, cnt + 1);add(v, u, c, cnt - 1);
        }int cct = 0;
        for (int i = 1;i <= n;++i) {
            if (!dfn[i]) {
                ++cct;
                tarjan(i, 0);
            }
        }if (cct > 1)cout << 0 << endl;
        else {
            int ans = 1e6;
            for (int i = 1;i < cnt;++i)
                if (is[i])
                    ans = min(E[i].cost, ans);
            if (ans == 1e6)cout << -1 << endl;
            else if (ans == 0)cout << 1 << endl;
            else cout << ans << endl;
        }
    }
}