Advertisement
limimage

Untitled

May 26th, 2019
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct DSU {
  4.   vector<int> p;
  5.   vector<int> d;
  6.   DSU(int n) {
  7.     p.resize(n);
  8.     for(int i=0;i<n;i++) {
  9.       p[i] = i;
  10.     }
  11.     d.assign(n, 1);
  12.   }
  13.   int get(int v) {
  14.     if(p[v] == v)
  15.       return v;
  16.     return p[v] = get(p[v]);
  17.   }
  18.   void uni(int a, int b) {
  19.     a = get(a);
  20.     b = get(b);
  21.     if(a!=b) {
  22.       if(d[a] < d[b]) {
  23.         swap(a,b);
  24.       }
  25.       d[a] += d[b];
  26.       p[b] = a;
  27.     }
  28.   }
  29. };
  30.  
  31. vector<pair<int,int> > edges;
  32. map<pair<int,int>, int> mp;
  33.  
  34. int main() {
  35.   ios_base::sync_with_stdio(false);
  36.   cin.tie(nullptr);
  37.  
  38.   int n,m;
  39.   cin>>n>>m;
  40.   set<pair<int,int> > arr[11];
  41.  
  42.   for(int i=0; i<m; i++) {
  43.     int f, t, w;
  44.     cin>>f>>t>>w;
  45.     f--,t--;
  46.     edges.push_back({f, t});
  47.     mp[{f,t}] = w;
  48.     arr[w].insert({f,t});
  49.   }
  50.  
  51.   vector<DSU> dsu(11, DSU(n));
  52.   int q;
  53.   cin>>q;
  54.   int answer = 0;
  55.   for(int i=0; i<=10; i++) {
  56.     for(int j=0; j<=i; j++) {
  57.       if(i == 10) {
  58.         for(pair<int,int> p : arr[j]) {
  59.           if(dsu[i].get(p.first) != dsu[i].get(p.second)) {
  60.             answer += mp[p];
  61.             dsu[i].uni(p.first, p.second);
  62.           }
  63.         }
  64.       }
  65.       for(pair<int,int> p : arr[j]) {
  66.         dsu[i].uni(p.first, p.second);
  67.       }
  68.     }
  69.   }
  70.  
  71.   while(q--) {
  72.     int i;
  73.     cin>>i;
  74.     i--;
  75.     pair<int,int> edge = edges[i];
  76.     int nextW = mp[edge] - 1;
  77.     mp[edge]--;
  78.     if(dsu[nextW].get(edge.first) != dsu[nextW].get(edge.second)) {
  79.             answer--;
  80.             dsu[nextW].uni(edge.first, edge.second);
  81.     }
  82.     cout<<answer<<'\n';
  83.   }
  84.  
  85.   return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement