fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_N = 2e5;
  18. const int LOG = 18;
  19.  
  20. struct Disjoint_Set_Union{
  21.     int leader[MAX_N + 5], rnk[MAX_N + 5];
  22.  
  23.     void build(int n){
  24.         FOR(i, 1, n){
  25.             leader[i] = i;
  26.             rnk[i] = 1;
  27.         }
  28.     }
  29.  
  30.     int get(int u){
  31.         if(u == leader[u]) return u;
  32.         return leader[u] = get(leader[u]);
  33.     }
  34.  
  35.     void unite(int u, int v){
  36.         int x = get(u), y = get(v);
  37.  
  38.         if(x == y) return;
  39.         if(rnk[x] < rnk[y]) swap(x, y);
  40.  
  41.         rnk[x] += rnk[y];
  42.         leader[y] = leader[x];
  43.     }
  44.  
  45.     bool is_joint(int u, int v){
  46.         return (leader[u] == leader[v]);
  47.     }
  48. }dsu;
  49.  
  50. struct Edge{
  51.     int u, v, w, id;
  52.  
  53.     bool operator < (const Edge &other) const{
  54.         return w < other.w;
  55.     }
  56. };
  57.  
  58. vector<int> adj[MAX_N + 5];
  59. bool in_mst[MAX_N + 5];
  60. bool vst[MAX_N + 5];
  61. int mst_sz;
  62.  
  63. vector<pii> g[MAX_N + 5];
  64. Edge edges[MAX_N + 5];
  65. int ans[MAX_N + 5];
  66. int n, m;
  67.  
  68. namespace Lowest_Common_Ancestor{
  69.     int par[LOG + 5][MAX_N + 5], depth[MAX_N + 5];
  70.     int mini[LOG + 5][MAX_N + 5];
  71.  
  72.     void dfs_lca(int u, int dad){
  73.         vst[u] = true;
  74.         for(int v : adj[u]) if(v != dad){
  75.             depth[v] = depth[u] + 1;
  76.             mini[0][v] = INF;
  77.             par[0][v] = u;
  78.  
  79.             dfs_lca(v, u);
  80.         }
  81.     }
  82.  
  83.     void build_lca(int n){
  84.         depth[0] = -1;
  85.         dfs_lca(1, -1);
  86.  
  87.         FOR(j, 1, LOG) FOR(i, 1, n){
  88.             par[j][i] = par[j - 1][par[j - 1][i]];
  89.             mini[j][i] = INF;
  90.         }
  91.     }
  92. }using namespace Lowest_Common_Ancestor;
  93.  
  94. void Input(){
  95.     cin >> n >> m;
  96.     FOR(i, 1, m){
  97.         int u, v, w;
  98.         cin >> u >> v >> w;
  99.  
  100.         g[u].pb({v, w});
  101.         g[v].pb({u, w});
  102.         edges[i] = {u, v, w, i};
  103.     }
  104. }
  105.  
  106. void kruskal(){
  107.     sort(edges + 1, edges + m + 1);
  108.     dsu.build(n);
  109.  
  110.     FOR(i, 1, m){
  111.         int u = edges[i].u, v = edges[i].v;
  112.         int w = edges[i].w, id = edges[i].id;
  113.  
  114.         if(dsu.get(u) != dsu.get(v)){
  115.             adj[u].pb(v);
  116.             adj[v].pb(u);
  117.             mst_sz += w;
  118.  
  119.             in_mst[id] = true;
  120.             dsu.unite(u, v);
  121.         }
  122.     }
  123. }
  124.  
  125. void Prepare(){
  126.     kruskal();
  127.     build_lca(n);
  128.  
  129.     FOR(i, 1, m) if(!in_mst[edges[i].id]){
  130.         int u = edges[i].u, v = edges[i].v;
  131.         int w = edges[i].w;
  132.  
  133.         if(depth[u] > depth[v]) swap(u, v);
  134.         REP(j, LOG, 0) if(depth[par[j][v]] >= depth[u]){
  135.             mini[j][v] = min(mini[j][v], w);
  136.             v = par[j][v];
  137.         }
  138.  
  139.         if(u == v) continue;
  140.         REP(j, LOG, 0) if(par[j][u] != par[j][v]){
  141.             mini[j][u] = min(mini[j][u], w);
  142.             mini[j][v] = min(mini[j][v], w);
  143.  
  144.             u = par[j][u];
  145.             v = par[j][v];
  146.         }
  147.  
  148.         mini[0][u] = min(mini[0][u], w);
  149.         mini[0][v] = min(mini[0][v], w);
  150.     }
  151.  
  152.     REP(j, LOG, 1) FOR(i, 1, n){
  153.         mini[j - 1][i] = min(mini[j - 1][i], mini[j][i]);
  154.         mini[j - 1][par[j - 1][i]] = min(mini[j - 1][par[j - 1][i]], mini[j][i]);
  155.     }
  156. }
  157.  
  158. void Solve(){
  159.     FOR(u, 1, n) if(!vst[u]){
  160.         FOR(i, 1, m) cout << -1 << el;
  161.         return;
  162.     }
  163.  
  164.     FOR(i, 1, m){
  165.         int u = edges[i].u, v = edges[i].v;
  166.         int w = edges[i].w, id = edges[i].id;
  167.         if(depth[u] > depth[v]) swap(u, v);
  168.  
  169.         if(!in_mst[id]) ans[id] = mst_sz;
  170.         else if(mini[0][v] != INF) ans[id] = mst_sz - w + mini[0][v];
  171.         else ans[id] = -1;
  172.     }
  173.     FOR(i, 1, m) cout << ans[i] << el;
  174. }
  175.  
  176. signed main(){
  177. //    freopen("silkroad.inp", "r", stdin);
  178. //    freopen("silkroad.out", "w", stdout);
  179.     ios_base::sync_with_stdio(0);
  180.     cin.tie(0);
  181.  
  182.     Input();
  183.     Prepare();
  184.     Solve();
  185.  
  186.     return 0;
  187. }
  188.  
Success #stdin #stdout 0.01s 17944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uTQE3n
language:
C++ (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!