Cod sursă (job #521002)

#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];
pair < int, pair <int , int> > krs[10005];
int ds[10005], N, M, K, minCost, h[10005], cnt;

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

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

void Union(int x, int y)
{
    x = root(x);
    y = root(y);
	if(h[x] > h[y])
        ds[y] = x;
    else
    {
        if(h[y] > h[x])
            ds[x] = y;
        else
        {
            ds[y] = x;
            h[x]++;
        }
    }
}

int Krusk(int lg)
{
	int c, x, y;
	for(int i = 1; i <= lg; i++){
		x = pr[i].second.first;
		y = pr[i].second.second;
		c = pr[i].first;
		if(root(x) != root(y)){
			minCost += c;
			krs[++cnt] = make_pair(c,make_pair(x,y));
			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(M) << "\n";
	for(int i = 1; i <= K; i++){
		minCost = 0;
		for(int i = 1; i <= cnt; i++){
            pr[i] = krs[i];
		}
		fin >> x >> y >> c;
		pr[++cnt] = make_pair(c,make_pair(x,y));
		for(int i = 1; i < cnt; i++){
            if(pr[cnt].first < pr[i].first){
                swap(pr[cnt],pr[i]);
                break;
            }
		}
		init();
		int aux = cnt;
		cnt = 0;
		fout << Krusk(aux) << "\n";
	}
	return 0;
}