Cod sursă (job #520991)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 110005
using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

pair < int , pair < int , int > > pr[NMAX];
int ds[NMAX], N, M, K, minCost;

void init()
{
	for(int i = 1; i <= N; i++){
		ds[i] = i;
	}
}

int root(int x)
{
    /*
	while(x != ds[x]){
		ds[x] = ds[ds[x]];
		x = ds[x];
	}
	*/
	if (ds[x] == x) return x;
	ds[x] = root(ds[x]);
	return ds[x];
}

void Union(int x, int y)
{
	int px = root(x);
	int py = root(y);
	ds[px] = py;
}

int Krusk()
{
	int c, x, y;
	for(int i = 1; i <= M; i++){
		x = pr[i].second.first;
		y = pr[i].second.second;
		c = pr[i].first;
		if(root(x) != root(y)){
			minCost += c;
			Union(x,y);
		}
	}
	return minCost;
}

int main()
{
	int x, y, c;
	fin >> N >> M >> K;
	for(int i = 1; i <= M; i++){
		fin >> x >> y >> c;
		pr[i] = make_pair(c,make_pair(x,y));
	}
	sort(pr + 1, pr + M + 1);
	init();
	fout << Krusk() << "\n";
	for(int i = 1; i <= K; i++){
		minCost = 0;
		M += 1;
		fin >> x >> y >> c;
		pr[M] = make_pair(c,make_pair(x,y));
		sort(pr + 1, pr + M + 1);
		init();
		fout << Krusk() << "\n";
	}
	return 0;
}