THACO2020: Superbridge

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 1e5 + 5;
const int logN = log2(1e5);
const int M = 2e5 + 5;
const int K = 3e5 + 5;

vector<pii> chosenLink;
vector<int> sortedEdges, normalMST, sortedLink;
tiii edges[M];
pii link[K];
int ds[N], sz[N];

bool compEdges(const int &lhs, const int &rhs){
    return get<2>(edges[lhs]) < get<2>(edges[rhs]);
}
bool compLinks(const int &lhs, const int &rhs){
    return link[lhs].second < link[rhs].second;
}

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

int main(){

    int nVertex, nEdge, nLink;
    scanf("%d%d%d", &nVertex, &nEdge, &nLink);
    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges[i] = tiii(u, v, w);
        sortedEdges.push_back(i);
    }
    sort(sortedEdges.begin(), sortedEdges.end(), compEdges);
    lli sumMST = 0;
    for(int i : sortedEdges){
        int u = get<0>(edges[i]);
        int v = get<1>(edges[i]);
        int w = get<2>(edges[i]);
        int ru = dsFind(u);
        int rv = dsFind(v);
        if(ru != rv){
            sumMST += w;
            normalMST.push_back(i);
            if(sz[ru] < sz[rv]){
                swap(ru, rv);
            }
            ds[rv] = ru;
            sz[ru] += sz[rv];
        }
    }
    for(int i = 1; i <= nLink; ++i){
        int u, w;
        scanf("%d%d", &u, &w);
        link[i] = pii(u, w);
        sortedLink.push_back(i);
    }
    sort(sortedLink.begin(), sortedLink.end(), compLinks);

    int upb;
    for(upb = 0; upb < sortedLink.size() && !normalMST.empty(); ++upb){
        int wl = link[sortedLink[upb]].second;
        int w = get<2>(edges[normalMST.back()]);
        if(wl >= w){
            break;
        }
        sumMST -= w - wl;
        normalMST.pop_back();
    }
    set<int> dsRemain;
    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        sz[i] = 1;
        dsRemain.insert(i);
    }
    for(int i : normalMST){
        int u = get<0>(edges[i]);
        int v = get<1>(edges[i]);
        u = dsFind(u);
        v = dsFind(v);
        if(sz[u] < sz[v]){
            swap(u, v);
        }
        ds[v] = u;
        sz[u] += sz[v];
        dsRemain.erase(v);
    }
    for(int i = 0; i < upb; ++i){
        int u = link[sortedLink[i]].first;
        u = dsFind(u);
        dsRemain.erase(u);
        int v = *dsRemain.begin();
        dsRemain.erase(v);
        chosenLink.emplace_back(sortedLink[i], v);
        if(sz[u] < sz[v]){
            swap(u, v);
        }
        ds[v] = u;
        sz[u] += sz[v];
        dsRemain.insert(u);
    }

    cout << sumMST << '\n' << normalMST.size() << '\n';
    for(int i : normalMST){
        cout << i << '\n';
    }
    cout << chosenLink.size() << '\n';
    for(pii p : chosenLink){
        cout << p.first << ' ' << p.second << '\n';
    }

    return 0;
}