Cod sursă (job #714289)

#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;
ll cost;
struct edge{
    int a, b, c;
    bool operator<(edge const& other) {
        return c < other.c;
    }
};
vector<edge>MinC,B;	
int find(int node){
    if(t[node]==node)
        return node;
    return t[node]=find(t[node]);
}
void Union(int x, int y){
    if(rang[x]>rang[y])
        t[y]=x, rang[x]+=rang[y];
    else
        t[x]=y, rang[y]+=rang[x];
}
 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());
	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;
}