Cod sursă (job #357371)

#include <bits/stdc++.h>

using namespace std;

#define nmax 10001
#define mmax 100001

int n, m, k;
struct edge {
    int from, to, cost;

    bool operator<(const edge& rhs) const {
        return cost < rhs.cost;
    }
};

edge edges[mmax];

int roots[nmax];
int ranks[nmax];
int last;

inline int get_root(int x) {
    int r = x;
    while (r != roots[r]) {
        r = roots[r];
    }

    int t;
    while (x != r) {
        t = roots[x];
        roots[x] = r;
        x = t;
    }
    return r;
}

inline void join(int x, int y) {
    int rx = get_root(x);
    int ry = get_root(y);

    if (ranks[ry] < ranks[rx]) {
        roots[ry] = rx;
    } else {
        roots[rx] = ry;
    }

    if (ranks[rx] == ranks[ry]) ranks[ry]++;
}

inline bool check(int x, int y) {
    return get_root(x) == get_root(y);
}

inline int apm() {
    int cost = 0;

    for (int i = 1; i <= n; i++) {
        roots[i] = i;
    }

    sort(edges, edges + last + 1);
    int cnt = 0;
    int new_last = 0;

    for (int i = 0; i <= last && cnt < n - 1; i++) {
        if (!check(edges[i].from, edges[i].to)) {
            join(edges[i].from, edges[i].to);
            cost += edges[i].cost;
            new_last = i;
        } else {
            edges[i].cost = 1 << 30;
        }
    }
    last = new_last;

    return cost;
}

int main() {
    freopen("carici.in", "r", stdin);

    freopen("zapada.in", "r", stdin);
    freopen("zapada.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &k);

    int x, y, c;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        edges[i] = {x, y, c};
    }

    sort(edges, edges + m);
    last = m - 1;
    cout << apm() << "\n";

    for (int i = 0; i < k; i++) {
        scanf("%d%d%d", &x, &y, &c);
        edges[++last] = {x, y, c};
        cout << apm() << "\n";
    }

    return 0;
}