Cod sursă (job #441133)

#include <bits/stdc++.h>

using namespace std;

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

int n, m, k, cmax, costArbore;
int mcx[101010], mcy[101010], costmc[101010], indicemc[101010], compConex[10005];

inline void citire()
{
    int x, y, c;
    in >> n >> m >> k;
    for (int i = 1; i <= m; ++i)
    {
        indicemc[i] = i;
        in >> mcx[i] >> mcy[i] >> costmc[i];
    }
}

inline bool cmp(int a, int b)
{
    return costmc[a] < costmc[b];
}

inline int grupa(int x)
{
    if (compConex[x] == x)
        return x;
    compConex[x] = grupa(compConex[x]);
    return compConex[x];
}

inline void reunire(int x, int y)
{
    compConex[grupa(x)] = grupa(y);
}

inline int cautBin(int lim)
{
    int poz = 1;
    for (int pas = 1 << 17; pas >= 1; pas >>= 1)
    {
        if (poz + pas <= m && costmc[indicemc[poz + pas]] <= lim)
            poz += pas;
    }
    return poz;
}


inline void generareAPM()
{
    for (int i = 1; i <= n; ++i)
        compConex[i] = i;
    cmax = 0;
    costArbore = 0;
    int nrMuchii = 0;
    for (int i = 1; nrMuchii < n - 1; ++i)
    {
        int x = mcx[indicemc[i]];
        int y = mcy[indicemc[i]];
        int c = costmc[indicemc[i]];
        if (grupa(x) != grupa(y))
        {
            ++nrMuchii;
            costArbore += c;
            cmax = max(cmax, c);
            reunire(x, y);
        }
    }
}

int main()
{
    citire();
    sort(indicemc + 1, indicemc + m + 1, cmp);
    generareAPM();
    out << costArbore << '\n';
    for (int q = 1; q <= k; ++q)
    {
        int x, y, c;
        in >> x >> y >> c;
        if (cmax < c)
            out << costArbore << '\n';
        else
        {
            int poz = cautBin(c);
            ++m;
            mcx[m] = x;
            mcy[m] = y;
            costmc[m] = c;
            for (int i = m; i >= poz; --i)
                indicemc[i] = indicemc[i - 1];
            indicemc[poz] = m;
            generareAPM();
            out << costArbore << '\n';
        }
    }
    return 0;
}