Cod sursă (job #718708)

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

class DSU {
	int* parent;
	int* rank;

public:
	DSU(int n) {
		parent = new int[n];
		rank = new int[n];

		for (int i = 0; i < n; i++) {
			parent[i] = -1;
			rank[i] = 1;
		}
	}

	int find(int i) {
		if (parent[i] == -1)
			return i;

		return parent[i] = find(parent[i]);
	}

	void unite(int x, int y) {
		int s1 = find(x);
		int s2 = find(y);

		if (s1 != s2) {
			if (rank[s1] < rank[s2]) {
				parent[s1] = s2;
			}
			else if (rank[s1] > rank[s2]) {
				parent[s2] = s1;
			}
			else {
				parent[s2] = s1;
				rank[s1] += 1;
			}
		}
	}
};

class Graph {
	vector<vector<int> > edgelist;
	int V;

public:
	Graph(int V) { this->V = V; }

	void addEdge(int x, int y, int w) {
		edgelist.push_back({ w, x, y });
	}

	void kruskals_mst() {
		sort(edgelist.begin(), edgelist.end());

		DSU s(V);
		int ans = 0;
		for (auto edge : edgelist) {
			int w = edge[0];
			int x = edge[1];
			int y = edge[2];

			if (s.find(x) != s.find(y)) {
				s.unite(x, y);
				ans += w;
			}
		}
		cout << ans << "\n";
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ifstream cin("zapada.in");
	ofstream cout("zapada.out");
	
	int N, M, K, x, y, c;
	cin >> N >> M >> K;
	
	Graph g(N);

	for (int i = 0; i < M; i++) {
		cin >> x >> y >> c;
		x--, y--;
		g.addEdge(x, y, c);
	}
	
	g.kruskals_mst();
	
	for (int i = 0; i < K; i++) {
		cin >> x >> y >> c;
		x--, y--;
		g.addEdge(x, y, c);
		g.kruskals_mst();
	}
	
	return 0;
}