Copa do mundo OBI 2014 fase 1

a.cpp

#include <bits/stdc++.h>
#define ii pair<int,int>
using namespace std;

const int N = 105;

int ds[N];

void dsBuild() {
    for(int i=0;i<N;i++) ds[i]=i;
}

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

void dsUnion(int a, int b) {
    a = dsFind(a), b = dsFind(b);
    if (a < b) swap(a, b);
    ds[b] = a;
}

int main() {
    int n,e1,e2;
    cin>>n>>e1>>e2;

    dsBuild();

    // {w, {a, b}}
    vector<pair<ii,ii>> edges;

    while(e1--) {
        int a,b,w; cin>>a>>b>>w;
        --a,--b;
        edges.push_back({{0,w},{a,b}});
    }

    while(e2--) {
        int a,b,w; cin>>a>>b>>w;
        --a,--b;
        edges.push_back({{1,w},{a,b}});
    }

    sort(edges.begin(), edges.end());

    int acc=0;

    for(auto p : edges) {
        int a = p.second.first, b = p.second.second;
        int w = p.first.second;

        if(dsFind(a) != dsFind(b)) {
            acc += w;
            dsUnion(a,b);
        }
    }

    cout<<acc<<'\n';

}