Cod sursă (job #759531)

#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;

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()+1,v.begin()+1+m,comp);
    
    for(int i=1;i<=n;++i) sz[i]=1,t[i]=i;
    cost_total=0;
    
    for(int i=1;i<=m;++i)
        if(find(v[i].x)!=find(v[i].y)){
            unio(v[i].x,v[i].y);
            cost_total+=v[i].c;
        }
    cout<<cost_total<<'\n';
}

int main()
{
    cin>>n>>m>>k;
    v.resize(m+1);
    
    for(int i=1;i<=m;++i)
        cin>>v[i].x>>v[i].y>>v[i].c;
    
    apm();
    
    for(int i=1;i<=k;++i){
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back({a,b,c});
        ++m;
        apm();
    }
    
    return 0;
}