Cod sursă (job #521730)

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

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

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

edge a[100005];

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;
}

vector <pair <int, int> > v[10005];

bool viz[10005];
int c[10005], h[10005];
void dfs(int nod = 1){
	viz[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it.first]) continue ;
		h[it.first] = h[nod] + 1;
		
		TT[it.first] = nod;
		c[it.first] = it.second;
		
		dfs(it.first);
	}
	viz[nod] = 0;
}

void del_edge(int x, int y){
	int pos = 0, sz = v[x].size();
	for(int i = 0; i < sz ; ++i){
		if(v[x][i].first == y){
			pos = i;
			break ;
		}
	}
	
	swap(v[x][pos], v[x][sz - 1]);
	v[x].pop_back();	
}

void new_apm(int x, int y, int C){
	int cost = 0, wx = x, wy = y, ax = x, ay = y;
	
	if(h[x] < h[y]) swap(x, y);
	while(x != y){
		if(h[x] == h[y]){
			if(c[y] > cost){
				wx = y; wy = TT[y];
				cost = c[y];
			}
			y = TT[y];
		}
		
		if(c[x] > cost){
			wx = x; wy = TT[x];
			cost = c[x];
		}		
		x = TT[x];
	}
	
	if(cost <= C){
		printf("%d\n", Sum);
		return ;
	}
	
	Sum = Sum + C - cost;
	printf("%d\n", Sum);

	del_edge(wx, wy);
	del_edge(wy, wx);

	v[ax].push_back({ay, C});
	v[ay].push_back({ax, C});
	
	dfs();
}

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);
	Sum = 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);
		
		v[a[i].x].push_back({a[i].y, a[i].c});
		v[a[i].y].push_back({a[i].x, a[i].c});
	}
	printf("%d\n", Sum);
	
	dfs();
	
	int x, y, c;
	for(int i = 1; i <= k ; ++i){
		scanf("%d%d%d", &x, &y, &c);
		
		new_apm(x, y, c);
	}
	
	return 0;
}