Cod sursă (job #625740)

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

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()
{
    freopen("zapada.in", "r", stdin);
    freopen("zapada.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d", &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;
    cnt=1;
    for(int i=0;i<m && cnt<n;i++)
    {
        int rx=root(mc[i].a);
        int ry=root(mc[i].b);
        if(rx!=ry)
        {
            cnt++;
            uneste(rx,ry);
            v.push_back(mc[i]);
            cost+=mc[i].c;
        }
    }
    printf("%d\n", cost);
    while(k--)
    {
        scanf("%d %d %d", &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;
            }
            cnt=1;
            for(int i=0;i<n && cnt<n;i++)
            {
                int rx=root(mc[i].a);
                int ry=root(mc[i].b);
                if(rx!=ry)
                {
                    cnt++;
                    uneste(rx,ry);
                    v.push_back(mc[i]);
                    cost+=mc[i].c;
                }
            }
            printf("%d\n", cost);
        }
        else
            printf("%d\n", cost);
    }
	return 0;
}