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