Cod sursă (job #720230)

#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;
	
}