fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define double long double
  5. #define all(v) v.begin(), v.end()
  6. #define ii pair<int, int>
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define maximize(a, b) a = max(a, b)
  11. #define minimize(a, b) a = min(a, b)
  12. #define cbit(n) __builtin_popcount(n)
  13. #define getbit(n, i) (n >> i) & 1
  14. #define onbit(n, i) n | (1 << i)
  15. #define offbit(n, i) n ^ (1 << i)
  16. #define TASK "1"
  17.  
  18. using namespace std;
  19.  
  20. const int N = 3e5 + 5;
  21. const ll oo = 1e18;
  22. const int base = 311;
  23. //const int sz = sqrt(N);
  24. const int mod = 1e9 + 7;
  25. int par[N], sz[N], h[N], mx[19][N], mx2[19][N], up[19][N], vis[N];
  26. int n, m;
  27. vector<ii> g[N];
  28.  
  29. struct edge
  30. {
  31.     int u, v, w;
  32.  
  33.     bool operator < (const edge &b) const
  34.     {
  35.         return w < b.w;
  36.     }
  37. } e[N];
  38.  
  39. void build(int u)
  40. {
  41.     sz[u] = 1;
  42.     par[u] = u;
  43. }
  44.  
  45. int f(int u) { return u == par[u] ? u : par[u] = f(par[u]); }
  46.  
  47. bool join(int u, int v)
  48. {
  49.     u = f(u);
  50.     v = f(v);
  51.     if(u != v){
  52.         if(sz[u] < sz[v]) swap(u, v);
  53.         sz[u] += sz[v];
  54.         par[v] = u;
  55.         return true;
  56.     }
  57.     return false;
  58. }
  59.  
  60. int max2(int a, int b, int c, int d)
  61. {
  62.     int mx = max(max(a, b), max(c, d));
  63.     int res = 0;
  64.     if(a != mx) maximize(res, a);
  65.     if(b != mx) maximize(res, b);
  66.     if(c != mx) maximize(res, c);
  67.     if(d != mx) maximize(res, d);
  68.     return res;
  69. }
  70.  
  71. void dfs(int u, int p)
  72. {
  73.     up[0][u] = p;
  74.     for(int i = 1; i <= 18; i++){
  75.         up[i][u] = up[i - 1][up[i - 1][u]];
  76.         mx[i][u] = max(mx[i - 1][u], mx[i - 1][up[i - 1][u]]);
  77.         mx2[i][u] = max2(mx2[i - 1][u], mx2[i -  1][up[i - 1][u]], mx[i - 1][u], mx[i - 1][up[i - 1][u]]);
  78.     }
  79.     for(ii v : g[u]){
  80.         if(v.fi == p) continue;
  81.         h[v.fi] = h[u] + 1;
  82.         mx[0][v.fi] = v.se;
  83.         dfs(v.fi, u);
  84.     }
  85. }
  86.  
  87. int lca(int u, int v, int w)
  88. {
  89.     int res = 0, res2 = 0;
  90.     if(h[u] != h[v]){
  91.         if(h[u] < h[v]) swap(u, v);
  92.         int d = h[u] - h[v];
  93.         for(int i = 18; i >= 0; i--){
  94.             if(getbit(d, i)){
  95.                 res2 = max2(mx[i][u], mx2[i][u], res, res2);
  96.                 maximize(res, mx[i][u]);
  97.                 u = up[i][u];
  98.             }
  99.         }
  100.     }
  101.     if(u == v) return (res == w ? res2 : res);
  102.     for(int i = 18; i >= 0; i--){
  103.         if(up[i][u] != up[i][v]){
  104.             res2 = max2(res2, mx[i][u], mx[i][v], mx2[i][v]);
  105.             res2 = max2(res2, mx[i][v], mx2[i][u], res);
  106.             maximize(res, mx[i][u]);
  107.             maximize(res, mx[i][v]);
  108.             u = up[i][u];
  109.             v = up[i][v];
  110.         }
  111.     }
  112.     res2 = max2(res2, mx[0][u], mx[0][v], mx2[0][v]);
  113.     res2 = max2(res2, mx[0][v], mx2[0][u], res);
  114.     maximize(res, mx[0][u]);
  115.     maximize(res, mx[0][v]);
  116.     if(res == w) return res2;
  117.     return res;
  118. }
  119.  
  120. signed main()
  121. {
  122.     ios_base::sync_with_stdio(false);
  123.     cin.tie(NULL);
  124.     cout.tie(NULL);
  125.  
  126.     if(fopen(TASK".inp", "r")){
  127.         freopen(TASK".inp", "r", stdin);
  128.         freopen(TASK".out", "w", stdout);
  129.     }
  130.  
  131.     cin >> n >> m;
  132.     for(int i = 1; i <= n; i++) build(i);
  133.     for(int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
  134.     sort(e + 1, e + 1 + m);
  135.     ll res = 0, cur = 0;
  136.     for(int i = 1; i <= m; i++){
  137.         if(join(e[i].u, e[i].v)){
  138.             cur += 1LL * e[i].w;
  139.             g[e[i].u].pb({e[i].v, e[i].w});
  140.             g[e[i].v].pb({e[i].u, e[i].w});
  141.             vis[i] = 1;
  142.         }
  143.     }
  144.     dfs(1, 0);
  145.     res = oo;
  146.     for(int i = 1; i <= m; i++){
  147.         if(!vis[i]){
  148. //            cerr << e[i].u << " " << e[i].v << " " << e[i].w << " " << lca(e[i].u, e[i].v) << "\n";
  149.             if(lca(e[i].u, e[i].v, e[i].w)) minimize(res, cur - 1LL * lca(e[i].u, e[i].v, e[i].w) + e[i].w);
  150.         }
  151.     }
  152.     cout << (res == oo ? -1 : res);
  153.     return 0;
  154. }
  155.  
Success #stdin #stdout 0.02s 75312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/gidrwT
language:
C++14 (gcc 8.3)
created:
3 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!