Cod sursă (job #624886)

#include <bits/stdc++.h>

using namespace std;

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


struct Elem
{
    int x , y, c;
    bool operator < (const Elem A) const
    {
        return c < A.c;
    }
};

Elem a[110005];
int n, m , k, t[10005];

void Union (int x , int y)
{
    t[x] = y;
}

int Find (int x)
{
    int rad = x;
    while (t[rad] != 0)
        rad = t[rad];
    int y = t[x];
    while (x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

void Kruskal ()
{
    int nrc = n;
    int cMin = 0;
    for (int i = 1; i <= n; i++)
        t[i] = 0;
    for (int i = 1; i <= m && nrc > 1; i++)
    {
        int x = Find(a[i].x);
        int y = Find(a[i].y);
        if (x != y)
        {
            nrc--;
            Union(x,  y);
            cMin += a[i].c;
        }
    }
    fout << cMin << "\n";
}


int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        fin >> a[i].x >> a[i].y >> a[i].c;
    sort (a + 1,  a + m + 1);
    ///for (int i = 1; i <= m; i++)
        ///fout << a[i].c << " ";
    Kruskal();
    for (int i = 1; i <= k; i++)
    {
        int x , y , c, j;
        fin >> x >> y >> c;
        m++;
        a[m] = {x, y, c};
        for (j = m - 1; j > 0 && a[j + 1].c < a[j].c; j--)
            swap (a[j], a[j + 1]);
        cout << j << " ";
        Kruskal();
    }
    return 0;
}