Cod sursă (job #719973)

#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;
	
 
	
// Creating shortcut for an integer pair
typedef pair<int, int> iPair;
  
// Structure to represent a graph
struct Graph
{
    int V, E;
    vector< pair<int, iPair> > edges;
  
    // Constructor
    Graph(int V, int E)
    {
        this->V = V;
        this->E = E;
    }
  
    // Utility function to add an edge
    void addEdge(int u, int v, int w)
    {
        edges.push_back({w, {u, v}});
    }
  
    // Function to find MST using Kruskal's
    // MST algorithm
    int kruskalMST();
};
  
// To represent Disjoint Sets
struct DisjointSets
{
    int *parent, *rnk;
    int n;
  
    // Constructor.
    DisjointSets(int n)
    {
        // Allocate memory
        this->n = n;
        parent = new int[n+1];
        rnk = new int[n+1];
        for (int i = 0; i <= n; i++)
        {
            rnk[i] = 0;
  
            //every element is parent of itself
            parent[i] = i;
        }
    }
    int find(int u)
    {

        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
  
    // Union by rank
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
  
        /* Make tree with smaller height
        a subtree of the other tree */
        if (rnk[x] > rnk[y])
            parent[y] = x;
        else // If rnk[x] <= rnk[y]
            parent[x] = y;
  
        if (rnk[x] == rnk[y])
            rnk[y]++;
    }
};
  
/* Functions returns weight of the MST*/
  
int Graph::kruskalMST()
{
    int mst_wt = 0;
    sort(edges.begin(), edges.end());
    DisjointSets ds(V);

    vector< pair<int, iPair> >::iterator it;
    for (it=edges.begin(); it!=edges.end(); it++)
    {
        int u = it->second.first;
        int v = it->second.second;
  
        int set_u = ds.find(u);
        int set_v = ds.find(v);
        if (set_u != set_v)
        {
            // Current edge will be in the MST
            // so print it
            
            
            //cout << u << " - " << v << endl;
  
  
            // Update MST weight
            mst_wt += it->first;
  
            // Merge two sets
            ds.merge(set_u, set_v);
        }
    }
  
    return mst_wt;
}
	
 
	
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;
	if(m>1000){
	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;
	}
	}
	else{
		int E=m+k;
    int x,y,weight;
    Graph g(n, E);
    for(int i=0;i<m;i++){
    	cin>>x;
    	cin>>y;
    	cin>>weight;
    	g.addEdge(x,y,weight);
	}
    int mst_wt = g.kruskalMST();
    cout<< mst_wt<<endl;
    for(int i=0;i<k;i++){
    	cin>>x;
    	cin>>y;
    	cin>>weight;
    	g.addEdge(x,y,weight);
    	mst_wt = g.kruskalMST();
    	cout<< mst_wt<<endl;
	}
	}	
	
}