Cod sursă (job #749924)

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

ifstream fin("zapada.in");
ofstream fout("zapada.out");

int n, m, k;
int a,b,c;
vector< tuple<int, short, short> > G;
short rep[10005];
uint64_t totalCost = 0;

void solve() {
    totalCost = 0;
    for(int k = 1; k <= n; ++k)
        rep[k] = k;
    for(const auto& conn : G) {
        tie(c,a,b) = conn;
        if(rep[a] == rep[b]) continue; // acelasi subarbore

        totalCost += c;
        short repa = rep[a], repb = rep[b];
        for(int k = 1; k <= n; ++k)
            if(rep[k] == repb) // acelasi reprezentat pt toti
                rep[k] = repa;
    }
    fout << totalCost << '\n';
}

int main()
{
    fin >> n >> m >> k;
    G.resize(m + k + 1);
    while(m--) {
        fin >> a >> b >> c;
        G.emplace_back(c,a,b);
    }
    sort(G.begin(), G.end()); // sortam primele m
    solve();
    while(k--) {
        fin >> a >> b >> c;
        G.emplace_back(c,a,b);
        sort(G.begin(), G.end());
        solve();
    }
    return 0;
}