Cod sursă (job #811851)

#include <fstream>
#include <set>

using namespace std;

ifstream in("zapada.in");
ofstream out("zapada.out");
int n, m, k;
set<pair<int, pair<int, int>>> s;
int tata[10005];
int dim[10005];

int rad(int x)
{
    if(x == tata[x])
    {
        return x;
    }

    int r = rad(tata[x]);
    tata[x] = r;
    return r;
}

void unire(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return;
    }

    if(dim[ry] > dim[rx])
    {
        swap(rx, ry);
    }

    tata[ry] = rx;
    dim[rx] += dim[ry];
}

int check(int x, int y)
{
    return (rad(x) == rad(y));
}

int main()
{
    in>>n>>m>>k;

    int x, y, z;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>z;

        s.insert({z, {x, y}});
    }

    for(int t = 0; t<=k; t++)
    {
        if(t != 0)
        {
            in>>x>>y>>z;

            s.insert({z, {x, y}});
        }

        for(int i = 1; i<=n; i++)
        {
            tata[i] = i;
            dim[i] = 1;
        }

        int cnt = n - 1;
        int ans = 0;
        for(auto it: s)
        {
            if(cnt == 0)
            {
                break;
            }

            if(check(it.second.first, it.second.second) == 0)
            {
                unire(it.second.first, it.second.second);
                ans += it.first;
                cnt--;
            }
        }

        out<<ans<<'\n';
    }

    return 0;
}