Cod sursă (job #759620)

#include <algorithm>
#include <fstream>
#include <vector>
#define dim 10002
using namespace std;
ifstream cin("zapada.in");
ofstream cout("zapada.out");
 
int n,m,cost_total,k;
int t[dim],sz[dim];
 
struct muchie{
    int x,y,c;
};
 
vector<muchie>v,arb;
 
bool comp(muchie a,muchie b){
    return a.c<b.c;
}
 
int find(int nod){
    while(t[nod]!=nod)
        nod=t[nod];
    return nod;
}
 
void unio(int a,int b){
    int ta=find(a),tb=find(b);
    if(sz[ta]>sz[tb]){
        t[tb]=ta;
        sz[ta]++;
    }else{
        t[ta]=tb;
        sz[tb]++;
    }
}
 
void apm(){
    sort(v.begin(),v.end(),comp);
    
    for(int i=1;i<=n;++i) sz[i]=1,t[i]=i;
    cost_total=0;
    
    for(auto mc:v)
        if(find(mc.x)!=find(mc.y)){
            unio(mc.x,mc.y);
            arb.push_back(mc);
            cost_total+=mc.c;
        }
    
    cout<<cost_total<<'\n';
}

void apm2(){
    
    for(int i=1;i<=n;++i) sz[i]=1,t[i]=i;
    cost_total=0;
    
    for(int i=0;i<n;++i){
        auto mc=v[i];
        if(find(mc.x)!=find(mc.y)){
            unio(mc.x,mc.y);
            arb.push_back(mc);
            cost_total+=mc.c;
        }
    }
    
    cout<<cost_total<<'\n';
}
 
int main()
{
    cin>>n>>m>>k;
    
    
    for(int i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back({a,b,c});
    }
    
    apm();
    // cout<<arb.size();
    for(int i=1;i<=k;++i){
        int a,b,c;
        cin>>a>>b>>c;
        if(c>=arb[arb.size()-1].c)
            cout<<cost_total<<'\n';
        else{
            arb.push_back({a,b,c});
            for(int i=arb.size()-1;i>0;i--)
                if(arb[i].c<arb[i-1].c)
                    swap(arb[i],arb[i-1]);
                else
                    break;
                    
            v=arb;
            arb.clear();
            
            for(int i=1;i<=n;++i) t[i]=i,sz[i]=1;
            apm2();
        }
    }
    
    return 0;
}