Advertisement
mickypinata

THACO2020: Superbridge

Nov 13th, 2021
1,137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6. typedef tuple<int, int, int> tiii;
  7.  
  8. const int N = 1e5 + 5;
  9. const int logN = log2(1e5);
  10. const int M = 2e5 + 5;
  11. const int K = 3e5 + 5;
  12.  
  13. vector<pii> chosenLink;
  14. vector<int> sortedEdges, normalMST, sortedLink;
  15. tiii edges[M];
  16. pii link[K];
  17. int ds[N], sz[N];
  18.  
  19. bool compEdges(const int &lhs, const int &rhs){
  20.     return get<2>(edges[lhs]) < get<2>(edges[rhs]);
  21. }
  22. bool compLinks(const int &lhs, const int &rhs){
  23.     return link[lhs].second < link[rhs].second;
  24. }
  25.  
  26. int dsFind(int u){
  27.     if(ds[u] == u){
  28.         return u;
  29.     }
  30.     return ds[u] = dsFind(ds[u]);
  31. }
  32.  
  33. int main(){
  34.  
  35.     int nVertex, nEdge, nLink;
  36.     scanf("%d%d%d", &nVertex, &nEdge, &nLink);
  37.     for(int i = 1; i <= nVertex; ++i){
  38.         ds[i] = i;
  39.         sz[i] = 1;
  40.     }
  41.     for(int i = 1; i <= nEdge; ++i){
  42.         int u, v, w;
  43.         scanf("%d%d%d", &u, &v, &w);
  44.         edges[i] = tiii(u, v, w);
  45.         sortedEdges.push_back(i);
  46.     }
  47.     sort(sortedEdges.begin(), sortedEdges.end(), compEdges);
  48.     lli sumMST = 0;
  49.     for(int i : sortedEdges){
  50.         int u = get<0>(edges[i]);
  51.         int v = get<1>(edges[i]);
  52.         int w = get<2>(edges[i]);
  53.         int ru = dsFind(u);
  54.         int rv = dsFind(v);
  55.         if(ru != rv){
  56.             sumMST += w;
  57.             normalMST.push_back(i);
  58.             if(sz[ru] < sz[rv]){
  59.                 swap(ru, rv);
  60.             }
  61.             ds[rv] = ru;
  62.             sz[ru] += sz[rv];
  63.         }
  64.     }
  65.     for(int i = 1; i <= nLink; ++i){
  66.         int u, w;
  67.         scanf("%d%d", &u, &w);
  68.         link[i] = pii(u, w);
  69.         sortedLink.push_back(i);
  70.     }
  71.     sort(sortedLink.begin(), sortedLink.end(), compLinks);
  72.  
  73.     int upb;
  74.     for(upb = 0; upb < sortedLink.size() && !normalMST.empty(); ++upb){
  75.         int wl = link[sortedLink[upb]].second;
  76.         int w = get<2>(edges[normalMST.back()]);
  77.         if(wl >= w){
  78.             break;
  79.         }
  80.         sumMST -= w - wl;
  81.         normalMST.pop_back();
  82.     }
  83.     set<int> dsRemain;
  84.     for(int i = 1; i <= nVertex; ++i){
  85.         ds[i] = i;
  86.         sz[i] = 1;
  87.         dsRemain.insert(i);
  88.     }
  89.     for(int i : normalMST){
  90.         int u = get<0>(edges[i]);
  91.         int v = get<1>(edges[i]);
  92.         u = dsFind(u);
  93.         v = dsFind(v);
  94.         if(sz[u] < sz[v]){
  95.             swap(u, v);
  96.         }
  97.         ds[v] = u;
  98.         sz[u] += sz[v];
  99.         dsRemain.erase(v);
  100.     }
  101.     for(int i = 0; i < upb; ++i){
  102.         int u = link[sortedLink[i]].first;
  103.         u = dsFind(u);
  104.         dsRemain.erase(u);
  105.         int v = *dsRemain.begin();
  106.         dsRemain.erase(v);
  107.         chosenLink.emplace_back(sortedLink[i], v);
  108.         if(sz[u] < sz[v]){
  109.             swap(u, v);
  110.         }
  111.         ds[v] = u;
  112.         sz[u] += sz[v];
  113.         dsRemain.insert(u);
  114.     }
  115.  
  116.     cout << sumMST << '\n' << normalMST.size() << '\n';
  117.     for(int i : normalMST){
  118.         cout << i << '\n';
  119.     }
  120.     cout << chosenLink.size() << '\n';
  121.     for(pii p : chosenLink){
  122.         cout << p.first << ' ' << p.second << '\n';
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
Advertisement
RAW Paste Data Copied
Advertisement