Advertisement
WayKillerZ

609E - MST For Each Edge

May 27th, 2022
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <iomanip>
  5. #include <cmath>
  6. #include <cstring>
  7. #include <climits>
  8. #include <cstdlib>
  9. #include <ctime>
  10.  
  11. #include <vector>
  12. #include <set>
  13. #include <bitset>
  14. #include <map>
  15. #include <queue>
  16. #include <deque>
  17. #include <stack>
  18. #include <string>
  19.  
  20. #define ll long long
  21. #define II pair<int, int>
  22. #define III pair<int, pair<int, int>>
  23. #define DI pair<double, int>
  24. #define fs first
  25. #define sc second
  26. #define mp(a, b) make_pair(a, b)
  27.  
  28. const ll LINF = 9223372036854775807;
  29. const int INF = 2147483647;
  30. const int MAX_N = 200005;
  31.  
  32. using namespace std;
  33.  
  34. int bit(int x, int k) {
  35.     return (1ll & (x >> k));
  36. }
  37.  
  38. struct Edge {
  39.     int u, v, w, id;
  40.     Edge(int u, int v, int w, int id) : u(u), v(v), w(w), id(id) {};
  41. };
  42.  
  43. struct Data {
  44.     int par;
  45.     ll maxc = -LINF;
  46. };
  47.  
  48. struct DSU {
  49.  
  50.     vector<int> par;
  51.    
  52.     void init(int n) {
  53.         par.resize(n+5, 0);
  54.         for(int i = 0; i <= n; i++) par[i] = -1;
  55.     }
  56.  
  57.     int find(int u) {
  58.         return (par[u] < 0 ? u : par[u] = find(par[u]));
  59.     }
  60.  
  61.     bool join(int u, int v) {
  62.         u = find(u); v = find(v);
  63.         if(u == v) return false;
  64.         par[v] = u;
  65.         return true;
  66.     }
  67.  
  68. } dsu;
  69.  
  70. int n, m, q, h[MAX_N];
  71. ll weight = 0;
  72. ll ans[MAX_N];
  73. Data up[MAX_N][22];
  74. vector<Edge> edges;
  75. vector<II> g[MAX_N];
  76.  
  77.  
  78. void dfs(int u, int p) {
  79.     up[u][0].par = p;
  80.  
  81.     for(auto& e : g[u]) {
  82.         int v = e.fs, c = e.sc;
  83.  
  84.         if(v == p) continue;
  85.         h[v] = h[u] + 1;
  86.         up[v][0].maxc = c;
  87.         dfs(v, u);
  88.     }
  89. }
  90.  
  91. void buildLCA() {
  92.     dfs(1, 1);
  93.     for (int i = 1; i <= 20; i++) {
  94.         for (int u = 1; u <= n; u++) {
  95.             up[u][i].par = up[up[u][i - 1].par][i - 1].par;
  96.             up[u][i].maxc = max(up[u][i - 1].maxc, up[up[u][i - 1].par][i - 1].maxc);
  97.         }
  98.     }
  99. }
  100.  
  101. ll solve(int u, int v) {
  102.    
  103.     ll ret;
  104.     if (h[u] < h[v]) swap(u, v);
  105.     int dep = h[u] - h[v];
  106.  
  107.     for (int i = 20; i >= 0; i--) {
  108.         if (bit(dep, i)) {
  109.             ret = max(ret, up[u][i].maxc);
  110.             u = up[u][i].par;
  111.         }
  112.     }
  113.  
  114.     if (u == v) return ret;
  115.    
  116.     for (int i = 20; i >= 0; --i) {
  117.         if (up[u][i].par != up[v][i].par) {
  118.             ret = max({ret, up[u][i].maxc, up[v][i].maxc});
  119.             u = up[u][i].par; v = up[v][i].par;
  120.         }
  121.     }
  122.  
  123.     return max({ret, up[u][0].maxc, up[v][0].maxc});
  124. }
  125.  
  126. int32_t main() {
  127.     ios_base::sync_with_stdio(false);
  128.     cin.tie(NULL);
  129.    
  130.     freopen("E.INP", "r", stdin);
  131.     freopen("E.OUT", "w", stdout);
  132.    
  133.     cin >> n >> m;
  134.    
  135.     int u, v, c;
  136.     for (int i = 1; i <= m; i++) {
  137.         cin >> u >> v >> c;
  138.         edges.push_back({u, v, c, i});
  139.     }
  140.  
  141.     dsu.init(n);
  142.  
  143.     sort(edges.begin(), edges.end(), [](Edge& a, Edge& b) {
  144.         return a.w < b.w;
  145.     });
  146.  
  147.     int cnt = 0;
  148.     for(auto& e : edges) {
  149.         if(!dsu.join(e.u, e.v)) continue;
  150.         cnt ++;
  151.         weight += e.w;
  152.         ans[e.id] = -1;
  153.         g[e.u].push_back({e.v, e.w});
  154.         g[e.v].push_back({e.u, e.w});
  155.         if(cnt == n) break;
  156.     }
  157.  
  158.     buildLCA();
  159.  
  160.     for(auto& e : edges) {
  161.         if(ans[e.id] == -1) ans[e.id] = weight;
  162.         else ans[e.id] = weight - solve(e.u, e.v) + e.w;
  163.     }
  164.  
  165.     for(int i = 1; i <= m; i++) cout << ans[i] << endl;
  166.     return 0;
  167. }
Advertisement
RAW Paste Data Copied
Advertisement