HDU 4738 Caocao's Bridges

题目链接

注意几个坑，可能重边，至少要派一个人去炸，没有连通的时候就不用炸了

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       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
      
        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; }