fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e5 + 5;
  5. const int M = __lg(MAXN) + 2;
  6. int n, m, ans_maxi;
  7. int h[MAXN], dist[MAXN], par[MAXN];
  8. int P[MAXN][M], Maxi[MAXN][M];
  9. vector<pair<int, int>> g[MAXN];
  10. vector<pair<int, pair<int, int>>> edge;
  11. bool mark[MAXN], vis[MAXN];
  12.  
  13. int find(int u) {
  14.     if (par[u] == u) return u;
  15.     return par[u] = find(par[u]);
  16. }
  17.  
  18. void join(int u, int v) {
  19.     int x = find(u);
  20.     int y = find(v);
  21.     if (x != y) par[x] = y;
  22. }
  23.  
  24. void DFS(int u) {
  25.     vis[u] = true;
  26.     for (int i = 1; i < M; i++) {
  27.         P[u][i] = P[P[u][i - 1]][i - 1];
  28.         Maxi[u][i] = max(Maxi[u][i - 1], Maxi[P[u][i - 1]][i - 1]);
  29.     }
  30.     for (int i = 0; i < g[u].size(); i++) {
  31.         int v = g[u][i].first;
  32.         int w = g[u][i].second;
  33.         if (!vis[v]) {
  34.             h[v] = h[u] + 1;
  35.             Maxi[v][0] = w;
  36.             P[v][0] = u;
  37.             DFS(v);
  38.         }
  39.     }
  40. }
  41.  
  42. int LCA(int u, int v) {
  43.     ans_maxi = 0;
  44.     if (h[u] < h[v]) swap(u, v);
  45.     int x = h[u] - h[v];
  46.     for (int i = __lg(x); i >= 0; i--) {
  47.         if (x >= (1 << i)) {
  48.             ans_maxi = max(ans_maxi, Maxi[u][i]);
  49.             u = P[u][i];
  50.             x -= (1 << i);
  51.         }
  52.     }
  53.     if (u == v) return u;
  54.     for (int i = __lg(h[u]); i >= 0; i--) {
  55.         if (P[u][i] != P[v][i]) {
  56.             ans_maxi = max({ans_maxi, Maxi[u][i], Maxi[v][i]});
  57.             u = P[u][i];
  58.             v = P[v][i];
  59.         }
  60.     }
  61.     ans_maxi = max({ans_maxi, Maxi[u][0], Maxi[v][0]});
  62.     return P[u][0];
  63. }
  64.  
  65. int main() {
  66.     ios::sync_with_stdio(0);
  67.     cin.tie(0);
  68.     cin >> n >> m;
  69.     for (int i = 1; i <= m; i++) {
  70.         int u, v, w;
  71.         cin >> u >> v >> w;
  72.         edge.push_back({w, {u, v}});
  73.     }
  74.     sort(edge.begin(), edge.end(), greater<>());
  75.     for (int i = 1; i <= n; i++) par[i] = i;
  76.     for (int id = 0; id < edge.size(); id++) {
  77.         int u = edge[id].second.first;
  78.         int v = edge[id].second.second;
  79.         int w = edge[id].first;
  80.         if (find(u) != find(v)) {
  81.             mark[id] = true;
  82.             join(u, v);
  83.             g[u].push_back({v, w});
  84.             g[v].push_back({u, w});
  85.         }
  86.     }
  87.     for (int i = 1; i <= n; i++) {
  88.         if (!vis[i]) DFS(i);
  89.     }
  90.     int ans = 0;
  91.     for (int id = 0; id < edge.size(); id++) {
  92.         if (!mark[id]) {
  93.             int w = edge[id].first;
  94.             int u = edge[id].second.first;
  95.             int v = edge[id].second.second;
  96.             LCA(u, v);
  97.             ans = max(ans, w + ans_maxi);
  98.         }
  99.     }
  100.     cout << ans;
  101. }
  102.  
Success #stdin #stdout 0.01s 7592KB
comments (?)
stdin
copy 
5 6 
4 5 4
4 1 4
1 5 1
1 2 3
2 3 2
1 3 3
stdout
copy 
5
https://ideone.com/DOAKF6
language:
C++14 (gcc 8.3)
created:
4 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!