Cod sursă (job #711073)

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn=10005;
int m,n,k,t[maxn],rang[maxn],a,b,c,cost;
struct edge{
	int a,b,c;	
};
vector<edge>MinC,B;	
bool cmp(edge x, edge y){
	return x.c<y.c;
}
int find(int node){
	while(node!=t[node]){
		node=t[node];
	}
	return node;
}
void Union(int x,int y){
	if(rang[x]>rang[y]){
		t[y]=x;
	}
	else{
		t[x]=y;
		if(rang[x]==rang[y]){
			rang[y]++;
		}
	}
}
 int main(){
 	ifstream cin("zapada.in");
 	ofstream cout("zapada.out");
 	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		cin >> a >> b >> c;
		MinC.pb({a,b,c});
	}
	sort(MinC.begin(),MinC.end(),cmp);
	for(int i=1;i<=n;i++){
		t[i]=i;
	}
	for(int i=0;i<m;i++){
		int x=find(MinC[i].a);
		int y=find(MinC[i].b);
		if(x!=y){
			Union(x,y);
			B.pb(MinC[i]);
			cost+=MinC[i].c;
		}
	}
	cout << cost << endl;
	while(k--){
		cin >> a >> b >> c;
		if(B[B.size()-1].c>c){
			B.pb({a,b,c});
			for(int i=B.size()-1;i>0;i--){
				if(B[i].c<B[i-1].c){
					swap(B[i],B[i-1]);
				}
				else break;
			}
			MinC=B;
			B.clear();
			cost=0;
			for(int i=1;i<=n;i++){
				t[i]=i;
				rang[i]=0;
			}
			for(int i=0;i<n;i++){
				int x=find(MinC[i].a);
				int y=find(MinC[i].b);
				if(x!=y){
					Union(x,y);
					B.pb(MinC[i]);
					cost+=MinC[i].c;
				}
			}
			cout << cost << endl;
		}
		else{
			cout << cost << endl;
		}
	}
 	return 0;
}