fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge {
  5.     int u, v;
  6.     long long w;
  7. };
  8.  
  9. int N, M;
  10. vector<Edge> edges;
  11.  
  12. bool ok(long long W) {
  13.     vector<vector<pair<int,int>>> adj(N+1);
  14.     int any = 0;
  15.     for (int i = 0; i < M; ++i) if (edges[i].w <= W) {
  16.         adj[edges[i].u].push_back({edges[i].v, i});
  17.         adj[edges[i].v].push_back({edges[i].u, i});
  18.         any = 1;
  19.     }
  20.     if (N == 1) return true;                     // 1 thành phố: luôn thỏa
  21.     if (!any) return false;                      // không có cạnh nào
  22.  
  23.     vector<int> disc(N+1, 0), low(N+1, 0);
  24.     int timer = 0; bool hasBridge = false;
  25.  
  26.     function<void(int,int)> dfs = [&](int u, int pe){
  27.         disc[u] = low[u] = ++timer;
  28.         for (auto [v, id] : adj[u]) {
  29.             if (id == pe) continue;
  30.             if (!disc[v]) {
  31.                 dfs(v, id);
  32.                 low[u] = min(low[u], low[v]);
  33.                 if (low[v] > disc[u]) hasBridge = true; // cầu
  34.             } else {
  35.                 low[u] = min(low[u], disc[v]);
  36.             }
  37.         }
  38.     };
  39.  
  40.     int start = 1;
  41.     while (start <= N && adj[start].empty()) ++start;
  42.     if (start > N) return false;                 // có đỉnh cô lập (N>1)
  43.  
  44.     dfs(start, -1);
  45.  
  46.     for (int i = 1; i <= N; ++i)
  47.         if (!disc[i]) return false;              // không liên thông
  48.  
  49.     return !hasBridge;
  50. }
  51.  
  52. int main() {
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.  
  56.     if (!(cin >> N >> M)) return 0;
  57.     edges.resize(M);
  58.     vector<long long> ws;
  59.     ws.reserve(M);
  60.     for (int i = 0; i < M; ++i) {
  61.         cin >> edges[i].u >> edges[i].v >> edges[i].w;
  62.         ws.push_back(edges[i].w);
  63.     }
  64.     sort(ws.begin(), ws.end());
  65.     ws.erase(unique(ws.begin(), ws.end()), ws.end());
  66.  
  67.     if (ws.empty()) {
  68.         cout << (N == 1 ? 0 : -1) << '\n';
  69.         return 0;
  70.     }
  71.  
  72.     // Nếu dùng tất cả cạnh vẫn không được → -1
  73.     if (!ok(ws.back())) {
  74.         cout << -1 << '\n';
  75.         return 0;
  76.     }
  77.  
  78.     int l = 0, r = (int)ws.size()-1, ans = r;
  79.     while (l <= r) {
  80.         int mid = (l + r) / 2;
  81.         if (ok(ws[mid])) { ans = mid; r = mid - 1; }
  82.         else l = mid + 1;
  83.     }
  84.     cout << ws[ans] << '\n';
  85.     return 0;
  86. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4
1 2 1
2 3 2
3 4 3
4 2 4
stdout
copy 
-1
https://ideone.com/JNZ52R
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!