Cod sursă (job #261853)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
    int x, y, c;
};
const int kMaxN = 10005;
vector <edge> v, mst;
int oldC, N, M, K, dad[kMaxN], dim[kMaxN];
bool comp(const edge &A, const edge &B) {
    return (A.c < B.c);
}
inline int compress(int x) {
    if (dad[x] == 0) return x;
    return (dad[x] = compress(dad[x]));
}
int initial_mst() {
    for (int i = 1; i <= N; ++i)
        dad[i] = 0, dim[i] = 1;
    int C = 0,rx, ry;
    for (size_t i = 0; i < v.size(); ++i) {
        rx = compress(v[i].x);
        ry = compress(v[i].y);
        if (rx != ry) {
            if (dim[rx] < dim[ry])
                dad[rx] = ry, dim[rx] += dim[ry];
            else
                dad[ry] = rx, dim[ry] += dim[rx];
            mst.push_back(v[i]);
            C += v[i].c;
        }
    }
    return C;
}
int update_mst(edge aux) {
    if (aux.c >= mst[mst.size() - 1].c)  return oldC;
    for (int i = 1; i <= N; ++i) dad[i] = 0, dim[i] = 1;
    int C = 0,rx, ry;
    bool ok = 0;
    size_t pos1 = 0, pos2 = 0;
    for (size_t i = 0; i < mst.size(); ++i) {
        if (!ok && aux.c < mst[i].c) {
            rx = compress(aux.x);
            ry = compress(aux.y);
            if (rx != ry) {
                if (dim[rx] < dim[ry]) dad[rx] = ry, dim[rx] += dim[ry];
                else dad[ry] = rx, dim[ry] += dim[rx];
                C += aux.c;
                pos1 = i;
            } else return oldC;
            ok = 1;
        }
        rx = compress(mst[i].x);
        ry = compress(mst[i].y);
        if (rx != ry) {
            if (dim[rx] < dim[ry]) dad[rx] = ry, dim[rx] += dim[ry];
            else dad[ry] = rx, dim[ry] += dim[rx];
            C += mst[i].c;
        } else pos2 = i;
    }
    for (size_t i = pos2; i > pos1; --i)
        swap(mst[i], mst[i - 1]);
    swap(mst[pos1], aux);
    return C;
}
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) {
        edge aux;
        scanf("%d%d%d", &aux.x, &aux.y, &aux.c);
        v.push_back(aux);
    }
    sort(v.begin(), v.end(), comp);
    printf("%d\n", (oldC = initial_mst()));
    for (int i = 1; i <= K; ++i) {
        edge aux;
        scanf("%d%d%d", &aux.x, &aux.y, &aux.c);
        printf("%d\n", (oldC = update_mst(aux)));
    }
    return 0;
}