Cod sursă (job #757189)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie {
    int i, j, cost;
};

int n, m, k, cnt, t[10003];
vector<pair<int, int>> v;
muchie x[110003];

void QuickSort(muchie v[], int st, int dr) {
    if (st < dr) {
        int m = (st + dr) / 2;
        swap(v[st], v[m]);
        int i = st, j = dr, d = 0;

        while (i < j) {
            if (v[i].cost > v[j].cost) {
                swap(v[i], v[j]);
                d = 1 - d;
            } else if (v[i].cost == v[j].cost) {
                if (v[i].i > v[j].i) {
                    swap(v[i], v[j]);
                    d = 1 - d;
                } else if (v[i].i == v[j].i && v[i].j > v[j].j) {
                    swap(v[i], v[j]);
                    d = 1 - d;
                }
            }
            if (d) i++;
            else j--;
        }

        QuickSort(v, st, i - 1);
        QuickSort(v, i + 1, dr);
    }
}

void Insert(int m, int st, int dr) {
    int poz = m;
    while (st <= dr) {
        int mijl = (st + dr) / 2;
        if (x[mijl].cost > x[m].cost) {
            poz = mijl;
            dr = mijl - 1;
        } else st = mijl + 1;
    }

    muchie aux = x[m];
    for (int i = m; i > poz; i--) {
        x[i] = x[i - 1];
    }
    x[poz] = aux;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin >> n >> m >> k;

    for (int i = 0; i < m; ++i)
        fin >> x[i].i >> x[i].j >> x[i].cost;

    sort(x, x + m, [](const muchie &a, const muchie &b) {
        return (a.cost == b.cost) ? ((a.i == b.i) ? (a.j < b.j) : (a.i < b.i)) : (a.cost < b.cost);
    });

    for (int l = 0; l < k; l++) {
        v.resize(0);

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

        int S = 0;
        for (int i = 0; i < m; i++)
            if (t[x[i].i] != t[x[i].j]) {
                S += x[i].cost;
                v.push_back(make_pair(x[i].i, x[i].j));
                int ai = t[x[i].i], aj = t[x[i].j];
                for (int j = 1; j <= n; ++j)
                    if (t[j] == aj)
                        t[j] = ai;
            }
        fout << S << "\n";
        fin >> x[m].i >> x[m].j >> x[m].cost;
        Insert(m, 0, m);
        m++;
    }

    Insert(m - 1, 0, m - 1);

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

    int S = 0;
    v.resize(0);

    for (int i = 0; i < m; i++)
        if (t[x[i].i] != t[x[i].j]) {
            S += x[i].cost;
            cnt++;
            v.push_back(make_pair(x[i].i, x[i].j));
            int ai = t[x[i].i], aj = t[x[i].j];
            for (int j = 1; j <= n; ++j)
                if (t[j] == aj)
                    t[j] = ai;
        }

    fout << S << "\n";
    fin.close();
    fout.close();

    return 0;
}