Cod sursă (job #719983)

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

int n, m, k, z, nr, ans, cmin, mx, sz;
int a, b, p[10005], h[10005];

struct zapada {
    int x, y;
    int c;
    bool operator < (const zapada &aux) const {
        return c < aux.c;
    }
} v[100005], pom[100005];

inline int find(int x) {
    int r = x;
    while(p[r] != r) r = p[r];
    while(p[x] != r) {
        int aux = p[x];
        p[x] = r;
        x = p[x];
    }
    return r;
}

inline void Union(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if(rx != ry) {
        if(h[rx] < h[ry]) 
			p[rx] = ry;
        else if(h[rx] > h[ry]) 
			p[ry] = rx;
        else {
            p[rx] = ry;
            h[ry]++;
        }
    }
}

inline void kruskal(zapada copac[],zapada v[],int m) {
    int cr = 0;
    cmin = 0;
    for(int i = 1;i <= n; i++) 
		p[i]=i;
    for(int i = m; i > 1; i--)
        if(copac[i].c < copac[i-1].c)
			swap(copac[i], copac[i-1]);
        else break;
    sz = 0;
    for(int i = 1; i <= m; i++) {
        if(find(copac[i].x) != find(copac[i].y)) {
            Union(copac[i].x, copac[i].y);
            cmin += copac[i].c;
            v[++sz] = copac[i];
            mx = copac[i].c;
            cr++;
        }
        if(cr == sz-1) break;
    }
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ifstream cin("zapada.in");
	ofstream cout("zapada.out");	
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
        cin >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1);
    kruskal(v, pom, m);
    cout << cmin << '\n';
    for(int i = 1; i <= k; i++) {
        cin >> a >> b >> z;
        if(z >= mx) {
            cout << cmin << '\n';
            continue;
        }
        else {
            sz++;
            pom[sz] = {a,b,z};
            kruskal(pom, pom, sz);
            cout << cmin << '\n';
        }
    }
    return 0;
}