Cod sursă (job #522548)

#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

ifstream in("zapada.in");
ofstream out("zapada.out");
int TT[10010];
int get_root(int x)
{
    int R = x;
    while(R != TT[R]) R = TT[R];
    while(TT[x] != x)
    {
        int y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}
struct bobu
{
    int x, y, c;
}G[100010];
bool cmp(bobu x, bobu y)
{
    return x.c < y.c;
}

int Sol, n, m, k, gx, gy;
void solve()
{
    for(int i = 1;i <= n;i++)
        TT[i] = i;
    sort(G + 1,G + m + 1, cmp);
    for(int i = 1;i <= m;i++)
    {
        gx = get_root(G[i].x);
        gy = get_root(G[i].y);
        if(gx != gy)
        {
            Sol += G[i].c;
            TT[gx] = gy;
        }
    }
    out << Sol << '\n';
}
int main()
{
    in >> n >> m >> k;
    for(int i = 1;i <= m;i++)
        in >> G[i].x >> G[i].y >> G[i].c;
    solve();
    while(k--)
    {
        m++;
        in >> G[m].x >> G[m].y >> G[m].c;
        Sol = 0;
        solve();
    }
    return 0;
}