Cod sursă (job #675968)

#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;
 
    int 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;
 
    int 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;
}