Cod sursă (job #625504)

// #include <iostream>
// #include <fstream>
#include <stdio.h>
#include <algorithm>

using namespace std;

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

int maxx = 0;
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;
            maxx = max(maxx, edges[i].first);
            cnt++;
            if ( cnt == n - 1 )
                break;
        }
    }
    edgesCnt = n - 1;

    return cost;
}

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);
        edges[++edgesCnt] = { c, {a, b} };
    }

    sort(edges + 1, edges + m + 1);
    printf("%d\n", kruskal());

    for ( int i = 1; i <= k; i++ )
    {
        scanf("%d %d %d", &a, &b, &c);
        edges[++edgesCnt] = { c, {a, b} };

        if ( c < maxx )
            for ( int i = edgesCnt; i > 1; i-- )
                if ( edges[i] < edges[i - 1] )
                    swap(edges[i], edges[i - 1]);
                else
                    break;
        maxx = 0;
        printf("%d\n", kruskal());
    }

}