Cod sursă (job #676733)

#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#define N 10005
using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");
int n, m, k, a, b, c;
int cost;
int t[N], viz[N], rang[N];
struct T { int a, b, c; };

vector<T>mc, v;
bool comp(T x, T y) { return x.c < y.c; }
int Rad(int x)
{
    while (x != t[x])x = t[x];
    return x;
}
void Uneste(int x, int y)
{
    if (rang[x] > rang[y])t[y] = x;
    else {
        t[x] = y;
        if (rang[x] == rang[y])
            rang[y]++;
    }
}
int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        mc.push_back({ a,b,c });
    }
    sort(mc.begin(), mc.end(), comp);
    for (int i = 1; i <= n; i++)t[i] = i;
    for (int i = 0; i < m; i++)
    {
        int rx = Rad(mc[i].a);
        int ry = Rad(mc[i].b);
        if (rx != ry)
        {
            Uneste(rx, ry);
            v.push_back(mc[i]);
            cost += mc[i].c;
        }
    }
    fout << cost << "\n";
    while (k--)
    {
        fin >> a >> b >> c;
        if (v[v.size() - 1].c > c)
        {
            v.push_back({ a,b,c });
            for (int i = v.size() - 1; i > 0; i--)
                if (v[i].c < v[i - 1].c)swap(v[i], v[i - 1]);
                else break;
            mc = v;
            v.clear();
            cost = 0;
            for (int i = 1; i <= n; i++) { t[i] = i; rang[i] = 0; }
            for (int i = 0; i < n; i++)
            {
                int rx = Rad(mc[i].a);
                int ry = Rad(mc[i].b);
                if (rx != ry)
                {
                    Uneste(rx, ry);
                    v.push_back(mc[i]);
                    cost += mc[i].c;
                }
            }
            fout << cost << "\n";
        }
        else fout << cost << "\n";
    }
    return 0;
}