Cod sursă (job #719462)

#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=10001;
using namespace std;
	
int t=1,n,m,k;
	
int parent[maxn],rang[maxn];
	
vector<pair<int,pair<int,int>>> A,B;
	
 
	
//DSU~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	
 
	
int find(int i){
	
	int ans;
	
	if(i==parent[i])ans=i;
	
	else{
	
		ans=find(parent[i]);
	
	}
	
	parent[i]=ans;
	
	return ans;
	
}
	
 
	
void unite(int i,int j){
	
	int i1=find(i);
	
	int j1=find(j);
	
	if(i1==j1)return;
	
	else if(rang[i1]>rang[j1]){
	
		parent[j1]=i1;
	
		rang[i1]=max(rang[i1],rang[j1]+1);
	
	}	
	
	else {
	
		parent[i1]=j1;
	
		rang[j1]=max(rang[j1],rang[i1]+1);
	
	}
	
}
	
 
	
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	
 
	
int createMST(){
	int ans=0;
	for(auto it:A){
		int a=it.S.F,b=it.S.S;
		int val=it.F;
		if(find(a)==find(b))continue;
		else{
			unite(a,b);
			B.push_back({val,{a,b}});
		}
		ans+=val;
	
	}
	
	return ans;
	
} 
	
 
	
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ifstream cin("zapada.in");
	ofstream cout("zapada.out");
	cin>>n>>m>>k;
	
	for(int i=0;i<m;i++){
	
		int c1,c2,c3;
	
		cin>>c1>>c2>>c3;
	
		A.push_back({c3,{c1-1,c2-1}});
	
	}
	
	for(int i=0;i<n;i++){
	
		parent[i]=i;
	
		rang[i]=1;
	
	}
	
	sort(A.begin(),A.end());
	
	int ans;
	
	ans=createMST();
	
	cout<<ans<<endl;
	
	A=B;
	
	while(k--){
	
		int c1,c2,c3;
	
		cin>>c1>>c2>>c3;
	
		vector<pair<int,pair<int,int>>>::iterator j,i;
	
		j=A.end();
	
		j--;
	
		while(j!=A.begin()&&j->F>c3){
	
			j--;
	
		}
	
		i=A.end();
	
		i--;
	
		if(j!=i){
	
			for(int i=0;i<n;i++){
	
				parent[i]=i;
	
				rang[i]=1;
	
			}
	
			A.insert(j,{c3,{c1-1,c2-1}});
	
			B.clear();
	
			ans=createMST();
	
		}
	
		A.clear();
	
		A=B;
		cout<<ans<<endl;
	
	}
	
}