首页 > 代码库 > HDU 4738 Caocao's Bridges(找割边)
HDU 4738 Caocao's Bridges(找割边)
HDU 4738 Caocao‘s Bridges
题目链接
注意几个坑,可能重边,至少要派一个人去炸,没有连通的时候就不用炸了
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 1005; const int INF = 0x3f3f3f3f; int pre[N], low[N], dfs_clock; int n, m; struct Node { int v, val, id; Node() {} Node(int v, int val, int id) { this->v = v; this->val = val; this->id = id; } }; vector<Node> g[N]; int ans; int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; int id = g[u][i].id; if (id == fa) continue; if (!pre[v]) { int lowv = dfs(v, id); lowu = min(lowu, lowv); if (lowv > pre[u]) ans = min(ans, g[u][i].val); } else lowu = min(lowu, pre[v]); } return low[u] = lowu; } int main() { while (~scanf("%d%d", &n, &m) && n) { int u, v, val; memset(pre, 0, sizeof(pre)); dfs_clock = 0; for (int i = 0; i < n; i++) g[i].clear(); for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &val); u--; v--; g[u].push_back(Node(v, val, i)); g[v].push_back(Node(u, val, i)); } int cnt = 0; ans = INF; for (int i = 0; i < n; i++) { if (!pre[i]) { cnt++; dfs(i, -1); } } if (cnt > 1) printf("0\n"); else if (ans == INF) printf("-1\n"); else { if (ans == 0) ans = 1; printf("%d\n", ans); } } return 0; }
HDU 4738 Caocao's Bridges(找割边)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。