Advertisement
YEZAELP

CUBE-199: Sagittarius A*

Sep 9th, 2020
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const lli INF = 2e18;
  7. using pi = pair <int, int>;
  8. using pli = pair <lli, int>;
  9. using P = pair <pli, pi>;
  10.  
  11. int n,m;
  12. int parent[100010];
  13.  
  14. int root(int u){
  15.     if(parent[u] == u) return u;
  16.     return parent[u] = root(parent[u]);
  17. }
  18.  
  19. void mrg(int u, int v){
  20.     u = root(parent[u]);
  21.     v = root(parent[v]);
  22.     parent[u] = v;
  23. }
  24.  
  25. int main(){
  26.  
  27.     scanf("%d%d", &n, &m);
  28.  
  29.     priority_queue <P> pq, keep;
  30.  
  31.     for(int i=1;i<=m;i++){
  32.         int u, v;
  33.         lli w;
  34.         scanf("%d%d%lld", &u, &v, &w);
  35.         pq.push({ {w, i}, {u, v}});
  36.         parent[u] = u;
  37.         parent[v] = v;
  38.     }
  39.     int t;
  40.     scanf("%d", &t);
  41.  
  42.     lli d = 0;
  43.     int cnt = 0;
  44.     set <int> line;
  45.     while(pq.size() > 0 and cnt < n){
  46.         int u, v, l;
  47.         lli w;
  48.         w = pq.top().first.first;
  49.         l = pq.top().first.second;
  50.         u = pq.top().second.first;
  51.         v = pq.top().second.second;
  52.         pq.pop();
  53.  
  54.         if(root(u) == root(v)) {
  55.             keep.push({ {w, l}, {u, v}});
  56.             continue;
  57.         }
  58.         mrg(u, v);
  59.  
  60.         d += w;
  61.         line.insert(l);
  62.         cnt++;
  63.     }
  64.  
  65.     while(keep.size() > 0 and cnt < n){
  66.         int u, v, l;
  67.         lli w;
  68.         w = keep.top().first.first;
  69.         l = keep.top().first.second;
  70.         u = keep.top().second.first;
  71.         v = keep.top().second.second;
  72.         keep.pop();
  73.         d += w;
  74.         line.insert(l);
  75.         cnt ++;
  76.     }
  77.  
  78.     if(cnt != n) {
  79.         printf("-1");
  80.         return 0;
  81.     }
  82.  
  83.     for(int i=1;i<=n;i++) {
  84.         if(root(parent[i]) != root(parent[1])) {
  85.             printf("-1");
  86.             return 0;
  87.         }
  88.     }
  89.  
  90.     printf("%lld\n",d);
  91.  
  92.     if(t == 1)
  93.         return 0;
  94.     for(auto l:line) printf("%d ",l);
  95.  
  96.     return 0;
  97. }
  98.  
Advertisement
RAW Paste Data Copied
Advertisement