Cod sursă (job #811871)

#include <fstream>
#include <set>

using namespace std;

ifstream in("zapada.in");
ofstream out("zapada.out");
int n, m, k;
pair<int, int> lat[101005];
set<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;

        lat[i] = {x, y};
        s.insert({z, i});
    }

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

            lat[m + t + 1] = {x, y};
            s.insert({z, m + t + 1});
        }

        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(lat[it.second].first, lat[it.second].second) == 0)
            {
                unire(lat[it.second].first, lat[it.second].second);
                ans += it.first;
                cnt--;
            }
        }

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

    return 0;
}