Cod sursă (job #720234)

#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;
typedef pair<int, int> iPair;
struct Graph
	{
    	int V, E;
    	vector< pair<int, iPair> > edges;
    	Graph(int V, int E)
    		{
        		this->V = V;
        		this->E = E;
    		}
    	void addEdge(int u, int v, int w)
    		{
        		edges.push_back({w, {u, v}});
    		}
    	int kruskalMST();
	};

struct DisjointSets
	{
    	int *parent, *rnk;
    	int n;
    	DisjointSets(int n)
    		{
        		this->n = n;
        		parent = new int[n+1];
        		rnk = new int[n+1];
        		for (int i = 0; i <= n; i++)
        			{
            			rnk[i] = 0;
            			parent[i] = i;
        			}
    		}
    	int find(int u)
    		{
 				if (u != parent[u])
            	parent[u] = find(parent[u]);
        		return parent[u];
    		}
    	void merge(int x, int y)
    		{
        		x = find(x), y = find(y);
        		if (rnk[x] > rnk[y]) parent[y] = x;
        			else parent[x] = y;
        		if (rnk[x] == rnk[y]) rnk[y]++;
    		}
	};
  
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)
					{	
            			mst_wt += it->first;
            			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 nMST()
	{
		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=nMST();
				cout<<ans<<'\n';
				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=nMST();
							}
						A.clear();
						A=B;
						cout<<ans<<endl;
					}
			}
			else
				{
					int E=m+k;
    				int x,y,greu;
    				Graph g(n, E);
    				for(int i=0;i<m;i++)
						{
    						cin>>x;
    						cin>>y;
    						cin>>greu;
    						g.addEdge(x,y,greu);
						}
    				int mst_wt = g.kruskalMST();
    				cout<< mst_wt<<endl;
    				for(int i=0;i<k;i++)
						{
    						cin>>x;
    						cin>>y;
    						cin>>greu;
    						g.addEdge(x,y,greu);
    						mst_wt = g.kruskalMST();
    						cout<< mst_wt<<endl;
						}
				}
	}