Cod sursă (job #14511)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct Edge {
	short int x, y, c;
};

class MyComp {
	public :
		bool operator () (const Edge &A, const Edge &B) {
			return A.c < B.c;
		}
};

multiset <Edge, MyComp> q;
const long M = 100005, K = 1002, N = 10005;
short int n, m, k, u = 0, lim ;
short int t [M], h [N];

void read () {
	short int i, xx, yy, cc;
	Edge temp;
	scanf ("%hd%hd%hd", &n, &m, &k);
	for (i = 0; i < m; i ++) {
		scanf ("%hd%hd%hd", &xx, &yy, &cc);
		temp.x = xx;
		temp.y = yy;
		temp.c = cc;
		q.insert (temp);
	}
}

void initializare () {
	short int i;
	for (i = 1; i <= n; i ++) {
		t [i] = i;
		h [i] = 1;
	}
}

short int getFather (const short int &x) {
	short int T, f;
	for (T = x; T != t [x]; T = t [x]);
	f = T;

	T = x;
	while (T != t [x]) {
		T = t [x];
		t [x] = f;
	}
	return f;
}

void unite (const short int &x, const short int &y) {
	if (h [x] >= h [y])
		t [y] = x;
	else
		t [x] = y;
	if (h [x] == h [y])
		h [x] ++;
}

long paduri () {
	short int num = 0, tx, ty, i;
	long s = 0;
	multiset <Edge, MyComp> :: iterator it;
	Edge o;
	initializare ();
	for (i = 0; i < lim; i ++) {
		it = q.begin ();
		advance (it, i);
		o = *it;
		tx = getFather (o.x);
		ty = getFather (o.y);
		if (tx != ty) {
			unite (tx, ty);
			num ++;
			s = (long)s + o.c;
		}
		if (num == n - 1)
			break;
	}
	return s;
}

void solve () {
	short int i, r, xx, yy, cc, minim, j;
	long c;
	Edge temp;

	lim = m;
	c = paduri ();
	printf ("%ld\n", c);

	for (i = 0; i < k; i ++) {
		scanf ("%hd%hd%hd", &xx, &yy, &cc);
		temp.x = xx;
		temp.y = yy;
		temp.c = cc;
		q.insert (temp);
		lim ++;
		c = paduri ();
		printf ("%ld\n", c);
	}
}

int main () {

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

	read ();
	solve ();
	return 0;
}