Cod sursă (job #711053)

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn=10007;
int n,m,k,t[maxn],rang[maxn],C[maxn];
struct edge{
	int a,b,c; 	
};
vector<edge>A,B;
bool comparare(edge x, edge y){
	return x.c<y.c;
}
int find(int x){
	int y; 
	int rang=x;
    while (t[rang]!=rang)
    	rang=t[rang];
    while (x!=rang){
        y=t[x];
        t[x]=rang;
        x=y;
    }
    return rang;
}
	
void unioni(int x, int y){
	t[y]=x;
}
 class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
 int main(){
 	ifstream fin("zapada.in");
 	ofstream fout("zapada.out");
	fin >> n >> m >> k;
	int z,q,c;
	for(int i=1;i<=m;i++){
		fin >> z >> q >> c;
		A.pb({z,q,c});
	}
	int cost=0;
//	cout <<endl;
	sort(A.begin(),A.end(),comparare);
//	for(auto v:A) cout << v.a << " " << v.b << " " << v.c << endl;
	for(int i=1;i<=n;i++){
		t[i]=i;
	}
	for(int i=0;i<m;i++){
		z=find(A[i].a);
		q=find(A[i].b);
		if(z!=q){
			unioni(z,q);
			B.pb(A[i]);
			cost+=A[i].c;
		}	
	}
	fout << cost << endl;
	while(k--){
		fin >> z >> q >> c;
		if(c<B[B.size()-1].c){
			B.pb({z,q,c});
		//	sort(B.begin(),B.end(),comparare);
			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;
			}
			A=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++){
				z=find(A[i].a);
				q=find(A[i].b);
				if(z!=q){
					unioni(z,q);
					B.pb(A[i]);
					cost+=A[i].c;
				}	
			}
			fout << cost << endl;
		}
		else fout << cost << endl;
	}
 	return 0;
}