Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define st first
  6. #define nd second
  7. #define int long long
  8.  
  9. typedef pair<int,int> pii;
  10. typedef pair<int,pii> piii;
  11. const int N = 2e5+5 , M = 64;
  12.  
  13. vector<piii> edges , MST;
  14. int n , m , tot , par[N] , vis[N] , sz[N] , h[N] , anc[N][M] , dist[N][M];
  15. vector<int> adj[N] , adjw[N];
  16. piii A[N];
  17.  
  18. int find(int a){return par[a] == a ? a : par[a] = find(par[a]);}
  19.  
  20. void unite(int x , int y){
  21.   x = find(x) , y = find(y);
  22.   if(x == y) return;
  23.   if(sz[x] < sz[y]) swap(x,y);
  24.   par[y]= x; sz[x] += sz[y];
  25. }
  26.  
  27. void Kruskal(){
  28.   sort(edges.begin(),edges.end());
  29.   for(auto e : edges)
  30.     if(find(e.nd.st) != find(e.nd.nd))
  31.       unite(e.nd.st , e.nd.nd) , MST.pb(e);
  32. }
  33.  
  34. void dfs(int u){
  35.   vis[u] = 1;
  36.   for(int i = 0 ; i < adj[u].size() ; i++){
  37.     int v = adj[u][i];
  38.     if(vis[v] == 0){
  39.       anc[v][0] = u  , dist[v][0] = adjw[u][i] , h[v] = h[u] + 1 , dfs(v) ;
  40.     }
  41.   }
  42. }
  43.  
  44. void build(){
  45.   for(int i = 1 ; i <= n ; i++){
  46.     for(int j = 1 ; j < M ; j++){
  47.       anc[i][j] = anc[anc[i][j-1]][j-1];
  48.       dist[i][j] = max(dist[i][j-1],dist[anc[i][j-1]][j-1]);
  49.     }
  50.   }
  51. }
  52.  
  53.  
  54. int lca(int u , int v){
  55.   int resp = 0;
  56.   if(h[u] < h[v]) swap(u,v);
  57.   for(int i = M-1 ; i >= 0 ; i--)
  58.     if(h[anc[u][i]] >= h[v]) resp = max(resp,dist[u][i]) , u = anc[u][i];
  59.   if(u == v) return resp;
  60.   for(int i = M-1 ; i>= 0 ; i--)
  61.     if(anc[u][i] != anc[v][i])
  62.       resp = max(resp,dist[v][i]) , resp = max(resp,dist[u][i]) , u = anc[u][i] , v = anc[v][i];
  63.  
  64.   return max(resp,max(dist[u][0],dist[v][0]));
  65. }
  66.  
  67. main(){
  68.  
  69.   cin >> n >> m;
  70.  
  71.   for(int i = 1 ; i <= n ; i++) par[i] = i , sz[i] = 1;
  72.  
  73.   for(int i = 1 ; i <= m ; i++){
  74.     int x , y , z;
  75.     cin >> x >> y >> z;
  76.     A[i] = {x,{y,z}};
  77.     edges.pb({z,{x,y}});
  78.   }
  79.  
  80.   Kruskal();
  81. //  cout << "aki:\n";
  82.  
  83.   //for(int i = 0 ; i < MST.size() ; i++)
  84.     //cout << MST[i].st << " " << MST[i].nd.st << " " << MST[i].nd.nd << "\n";
  85.  
  86.   for(int i = 0 ; i < MST.size() ; i++){
  87.     tot += MST[i].st;
  88.     adj[MST[i].nd.st].pb(MST[i].nd.nd) , adj[MST[i].nd.nd].pb(MST[i].nd.st);
  89.     adjw[MST[i].nd.st].pb(MST[i].st) , adjw[MST[i].nd.nd].pb(MST[i].st);
  90.   }
  91.  
  92.   h[1] = 1 , dfs(1) , build();
  93.  
  94.   //for(int i = 1 ; i <= n ; i++){
  95.     //for(int j = 0 ; j < 5 ; j++) cout << anc[i][j] << " ";
  96.     //cout << "\n";
  97.   //}
  98.   //cout << "\n";
  99.   //for(int i = 1 ; i <= n ; i++){
  100.     //for(int j = 0 ; j < 5 ; j++) cout << dist[i][j] << " ";
  101.     //cout << "\n";
  102.   //}
  103.  
  104.   for(int i = 1 ; i <= m ; i++)
  105.     cout << tot - lca(A[i].st,A[i].nd.st) + A[i].nd.nd << "\n";
  106.  
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement