Cod sursă (job #718709)

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

vector<int> parent, rank;
int N, M, K, x, y, c;

void make_set(int v) {
    parent[v] = v;
    ::rank[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (::rank[a] < ::rank[b])
            swap(a, b);
        parent[b] = a;
        if (::rank[a] == ::rank[b])
            ::rank[a]++;
    }
}

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

vector<Edge> edges;
vector<Edge> result;

void krusk() {
	int cost = 0;
	for (int i = 0; i < N; i++)
	    make_set(i);
	
	sort(edges.begin(), edges.end());
	
	for (Edge e : edges) {
	    if (find_set(e.u) != find_set(e.v)) {
	        cost += e.weight;
	        result.push_back(e);
	        union_sets(e.u, e.v);
	    }
	}
	cout << cost << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ifstream cin("zapada.in");
	ofstream cout("zapada.out");
	
	cin >> N >> M >> K;
	
	parent.resize(M + K);
	::rank.resize(M + K);

	for (int i = 0; i < M; i++) {
		cin >> x >> y >> c;
		x--, y--;
		edges.push_back({x, y, c});
	}
	
	krusk();
	
	for (int i = 0; i < K; i++) {
		cin >> x >> y >> c;
		x--, y--;
		edges.push_back({x, y, c});
		krusk();
	}
	
	return 0;
}