Cod sursă (job #521850)

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

struct edge{
	int x, y, c;
	bool operator < (const edge &aux)const{
		return c < aux.c;
	}
};

int n, m, k, Max;
int TT[10005], RG[10005];

edge a[100005];
edge b[10005];

inline int find(int x){
	int R = x;
	while(R != TT[R]) R = TT[R];
	
	while(TT[x] != R){
		int aux = TT[x];
		TT[x] = R;
		x = aux;
	}
	
	return R;
}

inline void unite(int x, int y){
	if(RG[x] > RG[y]) TT[y] = x;
	else if(RG[x] < RG[y]) TT[x] = y;
	else ++RG[x], TT[y] = x;
}

void apm(int m){
	for(int i = 1; i <= n ; ++i) TT[i] = i, RG[i] = 1;
	
	for(int i = m; i > 1 ; --i){
		if(b[i].c < b[i - 1].c) swap(b[i], b[i - 1]);
		else break ;
	}
	
	int Sum = 0, NR  = 0;
	for(int i = 1; i <= m ; ++i){
		int x = find(b[i].x), y = find(b[i].y);
		if(x == y) continue ;
	
		Sum = Sum + b[i].c;
		unite(x, y);
		b[++NR] = b[i];
		Max = b[i].c;
	}
	printf("%d\n", Sum);
}

int main(){
	freopen("zapada.in", "r", stdin);
	freopen("zapada.out", "w", stdout);
	
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m ; ++i)	
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
	
	for(int i = 1; i <= n ; ++i) TT[i] = i, RG[i] = 1;
	
	sort(a + 1, a + m + 1);
	int Sum = 0, NR = 0;
	for(int i = 1; i <= m ; ++i){
		int x = find(a[i].x), y = find(a[i].y);
		if(x == y) continue ;
	
		Sum = Sum + a[i].c;
		unite(x, y);
		b[++NR] = a[i];
		Max = a[i].c;
	}
	
	printf("%d\n", Sum);
	
	for(int i = 1; i <= k ; ++i){
		scanf("%d%d%d", &b[NR + 1].x, &b[NR + 1].y, &b[NR + 1].c);
		if(b[NR + 1].c >= Max){
			printf("%d\n", Sum);
			continue ;
		}
		apm(NR + 1);
	}
	
	return 0;
}