Cod sursă (job #521713)

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

ifstream f("zapada.in");
ofstream g("zapada.out");

const int maxn = 100001;

int gr[maxn],x[maxn],y[maxn],c[maxn];

int n,m,rez,ind[maxn],k;

int grupa(int i){
	if (gr[i] == i) return i;
	gr[i] = grupa(gr[i]);
	return gr[i];
}

void reuniune(int i,int j){
	gr[grupa(i)] = grupa(j);
}

bool cmp(int i,int j){
	return(c[i] < c[j]);
}

int main()
{
    f>>n>>m>>k;
	for(int i = 1;i <= m;++i)
	{
	    f>>x[i]>>y[i]>>c[i];
		ind[i] = i;
	}

	rez=0;
    for(int i = 1;i <= n; ++i) gr[i] = i;

    sort(ind+1, ind+m+1, cmp);

    for(int i = 1;i <= m; ++i){
        if (grupa(x[ind[i]]) != grupa(y[ind[i]])){
            rez += c[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
        }
    }
    g<<rez<<'\n';

	for(int pas=1; pas<=k; ++pas){

        rez=0;

        f>>x[m+pas]>>y[m+pas]>>c[m+pas];
        ind[pas+m]=pas+m;

        for(int i = 1;i <= n; ++i) gr[i] = i;

        sort(ind+1, ind+m+pas+1, cmp);

        for(int i = 1;i <= m+pas; ++i){
            if (grupa(x[ind[i]]) != grupa(y[ind[i]])){
                rez += c[ind[i]];
                reuniune(x[ind[i]],y[ind[i]]);
            }
        }
        g<<rez<<'\n';
	}

	return 0;
}