fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 3e5 + 5;
  5. const long long LOG = 20;
  6.  
  7. long long n,m;
  8. long long par[MaxN][LOG];
  9. long long mx1[MaxN][LOG],mx2[MaxN][LOG];
  10. long long d[MaxN];
  11.  
  12. vector<pair<long long,long long>> vt[MaxN];
  13. pair<long long,pair<long long,long long>> side[MaxN];
  14.  
  15. bool check[MaxN];
  16.  
  17. struct DSU
  18. {
  19.     long long lab[MaxN];
  20.  
  21.     void init()
  22.     {
  23.         for(long long i = 1; i <= n; i++)
  24.         {
  25.             lab[i] = -1;
  26.         }
  27.     }
  28.  
  29.     long long get_root(long long u)
  30.     {
  31.         if(lab[u] < 0)
  32.             return u;
  33.  
  34.         return lab[u] = get_root(lab[u]);
  35.     }
  36.  
  37.     void unite(long long u,long long v)
  38.     {
  39.         long long x = get_root(u);
  40.         long long y = get_root(v);
  41.  
  42.         if(x == y)
  43.             return;
  44.  
  45.         if(lab[x] > lab[y])
  46.             swap(x,y);
  47.  
  48.         lab[x] += lab[y];
  49.         lab[y] = x;
  50.     }
  51.  
  52.     bool check(long long u,long long v)
  53.     {
  54.         return get_root(u) == get_root(v);
  55.     }
  56. } dsu;
  57.  
  58. void dfs(long long u)
  59. {
  60.     for(auto x : vt[u])
  61.     {
  62.         long long v = x.first;
  63.         long long w = x.second;
  64.  
  65.         if(v == par[u][0])
  66.             continue;
  67.  
  68.         par[v][0] = u;
  69.         mx1[v][0] = w;
  70.         d[v] = d[u] + 1;
  71.  
  72.         dfs(v);
  73.     }
  74. }
  75.  
  76. void build()
  77. {
  78.     for(long long j = 1; j < LOG; j++)
  79.     {
  80.         for(long long i = 1; i <= n; i++)
  81.         {
  82.             par[i][j] = par[par[i][j-1]][j-1];
  83.  
  84.             long long a = mx1[i][j-1];
  85.             long long b = mx2[i][j-1];
  86.             long long c = mx1[par[i][j-1]][j-1];
  87.             long long e = mx2[par[i][j-1]][j-1];
  88.  
  89.             mx1[i][j] = max(a,c);
  90.  
  91.             mx2[i][j] = 0;
  92.  
  93.             if(a != mx1[i][j])
  94.                 mx2[i][j] = max(mx2[i][j],a);
  95.  
  96.             if(b != mx1[i][j])
  97.                 mx2[i][j] = max(mx2[i][j],b);
  98.  
  99.             if(c != mx1[i][j])
  100.                 mx2[i][j] = max(mx2[i][j],c);
  101.  
  102.             if(e != mx1[i][j])
  103.                 mx2[i][j] = max(mx2[i][j],e);
  104.         }
  105.     }
  106. }
  107.  
  108. pair<long long,long long> get_max(long long u,long long anc)
  109. {
  110.     long long ans1 = 0;
  111.     long long ans2 = 0;
  112.  
  113.     long long diff = d[u] - d[anc];
  114.  
  115.     for(long long i = LOG-1; i >= 0; i--)
  116.     {
  117.         if((diff >> i) & 1)
  118.         {
  119.             long long a = mx1[u][i];
  120.             long long b = mx2[u][i];
  121.  
  122.             if(a > ans1)
  123.             {
  124.                 ans2 = ans1;
  125.                 ans1 = a;
  126.             }
  127.             else if(a > ans2 && a != ans1)
  128.             {
  129.                 ans2 = a;
  130.             }
  131.  
  132.             if(b > ans2 && b != ans1)
  133.             {
  134.                 ans2 = b;
  135.             }
  136.  
  137.             u = par[u][i];
  138.         }
  139.     }
  140.  
  141.     return {ans1,ans2};
  142. }
  143.  
  144. long long lca(long long u,long long v)
  145. {
  146.     if(d[u] < d[v])
  147.         swap(u,v);
  148.  
  149.     for(long long i = LOG-1; i >= 0; i--)
  150.     {
  151.         if(d[par[u][i]] >= d[v])
  152.         {
  153.             u = par[u][i];
  154.         }
  155.     }
  156.  
  157.     if(u == v)
  158.         return u;
  159.  
  160.     for(long long i = LOG-1; i >= 0; i--)
  161.     {
  162.         if(par[u][i] != par[v][i])
  163.         {
  164.             u = par[u][i];
  165.             v = par[v][i];
  166.         }
  167.     }
  168.  
  169.     return par[u][0];
  170. }
  171.  
  172. void input()
  173. {
  174.     cin >> n >> m;
  175.  
  176.     for(long long i = 1; i <= m; i++)
  177.     {
  178.         long long u,v,w;
  179.         cin >> u >> v >> w;
  180.  
  181.         side[i] = {w,{u,v}};
  182.     }
  183. }
  184.  
  185. void solve()
  186. {
  187.     sort(side + 1,side + m + 1);
  188.  
  189.     dsu.init();
  190.  
  191.     long long mst_1 = 0;
  192.  
  193.     for(long long i = 1; i <= m; i++)
  194.     {
  195.         long long u = side[i].second.first;
  196.         long long v = side[i].second.second;
  197.         long long w = side[i].first;
  198.  
  199.         if(!dsu.check(u,v))
  200.         {
  201.             dsu.unite(u,v);
  202.             check[i] = true;
  203.             mst_1 += w;
  204.         }
  205.     }
  206.  
  207.     d[0] = -1;
  208.  
  209.     for(long long i = 1; i <= m; i++)
  210.     {
  211.         if(check[i])
  212.         {
  213.             long long u = side[i].second.first;
  214.             long long v = side[i].second.second;
  215.             long long w = side[i].first;
  216.  
  217.             vt[u].push_back({v,w});
  218.             vt[v].push_back({u,w});
  219.         }
  220.     }
  221.  
  222.     dfs(1);
  223.     build();
  224.  
  225.     long long mst_2 = LLONG_MAX;
  226.  
  227.     for(long long i = 1; i <= m; i++)
  228.     {
  229.         if(!check[i])
  230.         {
  231.             long long u = side[i].second.first;
  232.             long long v = side[i].second.second;
  233.             long long w = side[i].first;
  234.  
  235.             long long l = lca(u,v);
  236.  
  237.             pair<long long, long long> x = get_max(u,l);
  238.             pair<long long,long long> y = get_max(v,l);
  239.  
  240.             long long max1 = max(x.first,y.first);
  241.  
  242.             long long max2 = max(x.second,y.second);
  243.  
  244.             if(x.first != max1)
  245.                 max2 = max(max2,x.first);
  246.  
  247.             if(y.first != max1)
  248.                 max2 = max(max2,y.first);
  249.  
  250.             long long remove_edge;
  251.  
  252.             if(w > max1)
  253.                 remove_edge = max1;
  254.             else
  255.                 remove_edge = max2;
  256.  
  257.             if(remove_edge > 0)
  258.             {
  259.                 long long candidate = mst_1 - remove_edge + w;
  260.  
  261.                 if(candidate > mst_1)
  262.                     mst_2 = min(mst_2,candidate);
  263.             }
  264.         }
  265.     }
  266.  
  267.     cout << mst_2;
  268. }
  269.  
  270. int main()
  271. {
  272.     ios_base::sync_with_stdio(0);
  273.     cin.tie(0);
  274.  
  275.     input();
  276.     solve();
  277. }
Success #stdin #stdout 0.01s 11684KB
comments (?)
stdin 
Standard input is empty
stdout 
9223372036854775807
https://ideone.com/W2Ktah
language:
C++14 (gcc 8.3)
created:
1 day 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!