fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 1e5;
  12. const int maxlog = 20;
  13.  
  14. struct Edge
  15. {
  16.     int x, y;
  17.     ll w;
  18. };
  19.  
  20. int n, m, leader[maxn + 10], sz[maxn + 10], beg[maxn + 10], fin[maxn + 10], timer = 0;
  21. int par[maxn + 10][maxlog + 2];
  22. ll ans = 0, mx[maxn + 10][maxlog + 2];
  23. bool vis[maxn + 10];
  24. vector<ii> n_adj[maxn + 10];
  25. Edge e[maxn + 10];
  26. vector<Edge> notInMST;
  27.  
  28. bool cmp(Edge a, Edge b)
  29. {
  30.     return a.w > b.w;
  31. }
  32. int find_leader(int x)
  33. {
  34.     if (x == leader[x]) return x;
  35.     return leader[x] = find_leader(leader[x]);
  36. }
  37. bool connect(int x, int y)
  38. {
  39.     x = find_leader(x);
  40.     y = find_leader(y);
  41.     if (x == y) return 0;
  42.     if (sz[x] < sz[y]) swap(x, y);
  43.     sz[x] += sz[y];
  44.     leader[y] = x;
  45.     return 1;
  46. }
  47. void dfs(int top)
  48. {
  49.     vis[top] = 1;
  50.     beg[top] = ++timer;
  51.     for (ii pr : n_adj[top])
  52.     {
  53.         int next_top = pr.fi;
  54.         ll w = pr.se;
  55.         if (vis[next_top]) continue;
  56.         dfs(next_top);
  57.         mx[next_top][0] = w;
  58.         par[next_top][0] = top;
  59.     }
  60.     fin[top] = timer;
  61. }
  62. bool is_inside(int x, int y)
  63. {
  64.     if (!x) return 1;
  65.     return beg[x] <= beg[y] && fin[y] <= fin[x];
  66. }
  67. int getLCA(int x, int y)
  68. {
  69.     if (is_inside(x, y)) return x;
  70.     if (is_inside(y, x)) return y;
  71.     for (int i = maxlog; i >= 0; i--)
  72.         if (!is_inside(par[x][i], y))
  73.             x = par[x][i];
  74.     return par[x][0];
  75. }
  76. ll getmx(int x, int y)
  77. {
  78.     if (x == y) return 0;
  79.     ll ans = 0;
  80.     for (int i = maxlog; i >= 0; i--)
  81.         if (!is_inside(par[x][i], y))
  82.         {
  83.             ans = max(ans, mx[x][i]);
  84.             x = par[x][i];
  85.         }
  86.     return max(ans, mx[x][0]);
  87. }
  88.  
  89. int main()
  90. {
  91.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  92.     if (fopen("TROCHOI.INP", "r"))
  93.     {
  94.         freopen("TROCHOI.INP", "r", stdin);
  95.         freopen("TROCHOI.OUT", "w", stdout);
  96.     }
  97.  
  98.     cin >> n >> m;
  99.     for (int i = 1; i <= n; i++)
  100.     {
  101.         sz[i] = 1;
  102.         leader[i] = i;
  103.     }
  104.     for (int i = 1; i <= m; i++)
  105.     {
  106.         int x, y;
  107.         ll w;
  108.         cin >> x >> y >> w;
  109.         e[i] = {x, y, w};
  110.     }
  111.     sort(e + 1, e + m + 1, cmp);
  112.     for (int i = 1; i <= m; i++)
  113.     {
  114.         int x = e[i].x;
  115.         int y = e[i].y;
  116.         ll w = e[i].w;
  117.         if (connect(x, y))
  118.         {
  119.             n_adj[x].push_back({y, w});
  120.             n_adj[y].push_back({x, w});
  121.         }
  122.         else notInMST.push_back({x, y, w});
  123.     }
  124.     for (int i = 1; i <= n; i++)
  125.         if (!vis[i]) dfs(i);
  126.     for (int j = 1; j <= maxlog; j++)
  127.         for (int i = 1; i <= n; i++)
  128.         {
  129.             par[i][j] = par[par[i][j - 1]][j - 1];
  130.             mx[i][j] = max(mx[i][j - 1], mx[par[i][j - 1]][j - 1]);
  131.         }
  132.     for (Edge e : notInMST)
  133.     {
  134.         int x = e.x;
  135.         int y = e.y;
  136.         ll w = e.w;
  137.         int lca = getLCA(x, y);
  138.         ans = max(ans, max(getmx(x, lca), getmx(y, lca)) + w);
  139.     }
  140.     cout << ans;
  141. }
  142.  
Success #stdin #stdout 0.01s 7748KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dcGsg1
language:
C++14 (gcc 8.3)
created:
19 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!