fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const int N = 2e5+5;
  7. int n,m;
  8. struct Node
  9. {
  10.     int u,v,w,id;
  11. } edge[N];
  12. map<int,int> mp;
  13. bool cmp(const Node&a, const Node &b)
  14. {
  15.     return a.w < b.w;
  16. }
  17.  
  18. /// DSU để tìm cây khung
  19. int parent[N], sz[N];
  20. int find(int x)
  21. {
  22.     if(x == parent[x]) return x;
  23.     return parent[x] = find(parent[x]);
  24. }
  25.  
  26. /// LCA để tìm max
  27. vector<pair<int,int>> g[N];
  28.  
  29. int p[N][34], maxi[N][34], h[N];
  30.  
  31. void dfs(int u, int par)
  32. {
  33.     for(auto e : g[u])
  34.     {
  35.         int v = e.fi;
  36.         int w = e.se;
  37.         if(v != par)
  38.         {
  39.             p[v][0] = u;
  40.             h[v] = h[u] + 1;
  41.             maxi[v][0] = w;
  42.             dfs(v,u);
  43.         }
  44.     }
  45. }
  46.  
  47. void init()
  48. {
  49.     for(int j = 1; j <= 30; j++)
  50.     {
  51.         for(int i = 1; i <= n; i++)
  52.         {
  53.             maxi[i][j] = max(maxi[i][j-1], maxi[p[i][j-1]][j-1]);
  54.             p[i][j] = p[p[i][j-1]][j-1];
  55.         }
  56.     }
  57. }
  58.  
  59. int get_max(int u, int v)
  60. {
  61.     if(h[v] > h[u]) swap(v,u);
  62.     int x = h[u] - h[v];
  63.     int res = -1e18;
  64.     for(int i = 30; i >= 0; i--)
  65.     {
  66.         if(x >= (1 << i))
  67.         {
  68.             res = max(res, maxi[u][i]);
  69.             u = p[u][i];
  70.             x -= (1 << i);
  71.         }
  72.     }
  73.  
  74.     if(u == v) return res;
  75.  
  76.     for(int i = 30; i >= 0; i--)
  77.     {
  78.         if(p[u][i] != p[v][i])
  79.         {
  80.             res = max({res, maxi[u][i], maxi[v][i]});
  81.             u = p[u][i];
  82.             v = p[v][i];
  83.         }
  84.     }
  85.     return max({res, maxi[u][0], maxi[v][0]});
  86. }
  87.  
  88.  
  89. /// KẾT QUẢ
  90.  
  91. int ans[N];
  92. bool check[N];
  93. main()
  94. {
  95.     ios_base::sync_with_stdio(false);
  96.     cin.tie(NULL);
  97. //    freopen("spanedge.inp", "r", stdin);
  98. //    freopen("spanedge.out", "w", stdout);
  99.     cin >> n >> m;
  100.     /// KHAI BÁO DSU VÀ NHẬP CẠNH
  101.     for(int i = 1; i <= n; i++) parent[i] = i;
  102.     for(int i = 1; i <= m; i++)
  103.     {
  104.         cin >> edge[i].u >> edge[i].v >> edge[i].w;
  105.         edge[i].id = i;
  106.     }
  107.  
  108.     /// SORT TĂNG DẦN ĐỂ TÌM CÂY KHUNG BÉ NHẤT
  109.     sort(edge+1,edge+1+m,cmp);
  110.  
  111.  
  112.     /// DỰNG CÂY KHUNG
  113.     int total = 0;
  114.     int W = 0;
  115.     for(int i = 1; i <= m; i++)
  116.     {
  117.         int u = edge[i].u;
  118.         int v = edge[i].v;
  119.         int w = edge[i].w;
  120.         int id = edge[i].id;
  121.  
  122.         int x = find(u);
  123.         int y = find(v);
  124.         if(x != y)
  125.         {
  126.             if(sz[x] < sz[y]) swap(x,y);
  127.             parent[y] = x;
  128.             sz[x] += sz[y];
  129.             W += w;
  130.             total++;
  131.             mp[id] = 1;
  132.             g[u].push_back({v,w});
  133.             g[v].push_back({u,w});
  134.         }
  135.         if(total == n - 1) break;
  136.     }
  137.  
  138.     dfs(1,-1);
  139.     init();
  140.  
  141.     for(int i = 1; i <= m; i++)
  142.     {
  143.         int u = edge[i].u;
  144.         int v = edge[i].v;
  145.         int w = edge[i].w;
  146.         int id = edge[i].id;
  147.         /// Nếu cạnh này đã check rồi thì bỏ đi
  148.         if(mp[id] == 1) mp[id] = W;
  149.         else mp[id] = W - get_max(u,v) + w;
  150.     }
  151.  
  152.     for(int i = 1; i <= m; i++)
  153.         cout << mp[i] << "\n";
  154.  
  155. }
  156.  
Success #stdin #stdout 0.01s 11824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rhI4qK
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!