Cod sursă (job #625509)

#include <stdio.h>
#include <algorithm>

using namespace std;

int maxx = 0;
int n, m, k, a, b, c, edgesCnt, root[10005], sz[10005];
pair<int, pair<int, int>> edges[100005];

inline void link(int x, int y)
{
    if ( sz[y] < sz[x] )
        root[y] = x, sz[x] += sz[y];
    else
        root[x] = y, sz[y] += sz[x];
}

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

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

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

    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);
            if ( ck == n - 1 )
                break;
        }
    }
    edgesCnt = n - 1;

    printf("%d\n", 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);
    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;
        kruskal();
    }

}