Cod sursă (job #625492)

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

using namespace std;

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

int n, m, k, a, b, c, edgesCnt, root[10005];
pair<int, pair<int, int>> edges[101005];

void link(int x, int y)
{
    root[y] = x;
}

int getRoot(int x)
{
    if ( x != root[x] )
        root[x] = getRoot(root[x]);
    return root[x];
}

int kruskal()
{
    int cost = 0, cnt = 0, ck = 0;

    for ( int i = 1; i <= n; i++ )
        root[i] = i;

    for ( int i = 1; i <= edgesCnt; i++ )
    {
        a = getRoot(edges[i].second.first);
        b = getRoot(edges[i].second.second);

        if ( a != b )
        {
            link(a, b);
            edges[++ck] = edges[i];
            cost += edges[i].first;
            cnt++;
            if ( cnt == n - 1 )
                break;
        }
    }
    edgesCnt = n - 1;

    return cost;
}

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

    for ( int i = 1; i <= m; i++ )
    {
        fin >> a >> b >> c;
        edges[++edgesCnt] = { c, {a, b} };
    }

    sort(edges + 1, edges + m + 1);
    fout << kruskal() << "\n";

    for ( int i = 1; i <= k; i++ )
    {
        fin >> a >> b >> c;
        edges[++edgesCnt] = { c, {a, b} };

        for ( int i = edgesCnt; i > 1; i-- )
            if ( edges[i] < edges[i - 1] )
                swap(edges[i], edges[i - 1]);
            else
                break;

        fout << kruskal() << "\n";
    }

}