Cod sursă (job #757149)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

const int MAX=10005;
int n,m,k,cnt,a,b,c,cost,mi,r1,r2,ok,t[MAX],rang[MAX],viz[MAX];
struct T{int a,b,c;};
vector < T > mc,v;

bool cmp(T x, T y)
{
    return x.c<y.c;
}

int root(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}

void uneste(int x, int y)
{
    if(rang[x]>rang[y])
        t[y]=x;
    else
    {
        t[x]=y;
        if(rang[x]==rang[y])
            rang[y]++;
    }
}

int main()
{
    fin >> n >> m >> k;
    for(int i=1;i<=m;i++)
    {
        fin >> a >> b >> c;
        mc.push_back({a,b,c});
    }
    sort(mc.begin(),mc.end(),cmp);
    for(int i=1;i<=n;i++)
        t[i]=i;
    for(int i=0;i<m;i++)
    {
        int rx=root(mc[i].a);
        int ry=root(mc[i].b);
        if(rx!=ry)
        {
            uneste(rx,ry);
            v.push_back(mc[i]);
            cost+=mc[i].c;
        }
    }
    fout << cost << '\n';
    while(k--)
    {
        fin >> a >> b >> c;
        if(v[v.size()-1].c>c)
        {
            v.push_back({a,b,c});
            for(int i=v.size()-1;i>0;i--)
                if(v[i].c<v[i-1].c)
                    swap(v[i],v[i-1]);
                else
                    break;
            mc=v;
            v.clear();
            cost=0;
            for(int i=1;i<=n;i++)
            {
                t[i]=i;
                rang[i]=0;
            }
            for(int i=0;i<n;i++)
            {
                int rx=root(mc[i].a);
                int ry=root(mc[i].b);
                if(rx!=ry)
                {
                    uneste(rx,ry);
                    v.push_back(mc[i]);
                    cost+=mc[i].c;
                }
            }
            fout << cost << '\n';
        }
        else
            fout << cost << '\n';
    }
	return 0;
}