Cod sursă (job #720232)

#include<bits/stdc++.h>
	
using namespace std;
	
 
	
// 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 main(){
	
	ios_base::sync_with_stdio(false);
	
	cin.tie(NULL);
	
	freopen("zapada.in","r",stdin);
	
	freopen("zapada.out","w",stdout);
	
    int V, E,M,K,x,y,weight;
	
    cin>>V;
	
    cin>>M;
	
    cin>>K;
	
    E=M+K;
	
    
	
    Graph g(V, 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;
	
	}
	
    return 0;
	
}