fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define maxn 1000005
  3. #define maxm 10000005
  4. #define maxc 1000000007
  5. #define mp make_pair
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define pii pair<long long, long long>
  10. #define fort(i, a, b) for(int i = (a); i <= (b); i++)
  11. #define ford(i, a, b) for(int i = (a); i >= (b); i--)
  12. #define Task "UPGRANET"
  13. #define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
  14. #define stop1 {cout << "-1\n"; return;}
  15. #define stop2 {cout << "0\n"; return;}
  16. #define stop3 {cout << "yes\n"; exit(0);}
  17. #define skip1 {cout << "Yes\n"; continue;}
  18. #define skip2 {cout << "No\n"; continue;}
  19. #define ll long long
  20.  
  21. using namespace std;
  22.  
  23. ll n, m, root[maxn], h[maxn], res;
  24. pii  par[maxn][20];
  25. bool dd[maxn];
  26. vector<pair<ll, ll> > ke[maxn];
  27. struct canh
  28. {
  29.     ll u, v, w;
  30. }ed[maxn];
  31.  
  32. void setup()
  33. {
  34.     cin >> n >> m;
  35.     fort(i, 1, m)
  36.         cin >> ed[i].u >> ed[i].v >> ed[i].w;
  37. }
  38.  
  39. bool cmp(canh p, canh q)
  40. {
  41.     return p.w > q.w;
  42. }
  43.  
  44. ll getroot(ll u)
  45. {
  46.     if(root[u] == 0) return u;
  47.     return root[u] = getroot(root[u]);
  48. }
  49.  
  50. void make_tree()
  51. {
  52.     sort(ed+1, ed+m+1, cmp);
  53.     fort(i, 1, m)
  54.     {
  55.         ll p = getroot(ed[i].u);
  56.         ll q = getroot(ed[i].v);
  57.         if(p == q) continue;
  58.         root[p] = q;
  59.         dd[i] = 1;
  60.         ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
  61.         ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
  62.     }
  63. }
  64.  
  65. void dfs(ll u, ll tr)
  66. {
  67.     fort(i, 0, int(ke[u].size()) - 1)
  68.     {
  69.         ll v = ke[u][i].F;
  70.         if(v == tr) continue;
  71.         h[v] = h[u] + 1;
  72.         par[v][0] = mp(u,ke[u][i].S);
  73.         fort(j, 1, 18)
  74.         {
  75.             par[v][j].F = par[par[v][j-1].F][j-1].F;
  76.             par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
  77.         }
  78.         dfs(v, u);
  79.     }
  80. }
  81.  
  82. pii lca(ll u, ll v)
  83. {
  84.     pii p;
  85.     p.S = 1ll* maxc * maxc;
  86.     if( h[u] > h[v])
  87.         swap(u, v);
  88.     ll diff = h[v] - h[u];
  89.     ford(i, 18, 0)
  90.         if((diff >> i) & 1)
  91.         {
  92.             p.S = min(p.S, par[v][i].S);
  93.             v = par[v][i].F;
  94.  
  95.         }
  96.     if(v == u) return mp(u, p.S);
  97.     ford(i, 18, 0)
  98.         if(par[u][i].F != par[v][i].F)
  99.         {
  100.             p.S = min(p.S, min(par[v][i].S, par[u][i].S));
  101.             v = par[v][i].F;
  102.             u = par[u][i].F;
  103.         }
  104.     return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
  105. }
  106.  
  107. void work()
  108. {
  109.     make_tree();
  110.     h[1] = 1;
  111.     dfs(1, 0);
  112.     fort(i, 1, m)
  113.         if(!dd[i])
  114.         {
  115.             pii l = lca(ed[i].u, ed[i].v);
  116.             res += max(0ll, l.S - ed[i].w);
  117.         }
  118.     cout << res;
  119. }
  120.  
  121.  
  122. int main()
  123. {
  124.     fast
  125.   //  freopen(Task".inp", "r", stdin);
  126.   //  freopen(Task".out", "w", stdout);
  127.     setup();
  128.     work();
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0s 391232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aSyTG1
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!