Cod sursă (job #334505)

#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() {
	int player_unu=0;

    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 player_unu;
}
//#include <iostream>
//#include <stdio.h>
//#include <stdlib.h>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 10010 ;
//
//struct Muchie {
//    int x , y , cost ;
//};
//
//vector < Muchie > mucInit ;
//int noNodes , noMuc , noUpgrades ;
//Muchie sol [ N ] ;
//int noApm ;
//int tat [ N ] , dim [ N ] ;
//char readBuffer [ 50 ];
//
//int findTat ( int x ){
//    static int tatx , tx ;
//
//    tatx = x ;
//    while ( tat [ tatx ] > 0 ){
//        tatx = tat[ tatx ];
//    }
//
//    while ( tat [ x ] > 0 ){
//        tx = tat [ x ];
//        tat [ x ] = tatx ;
//        x = tx ;
//    }
//
//    return tatx ;
//}
//
//int mergeTat ( int x , int y ){
//    int tatx , taty ;
//
//    tatx = findTat ( x );
//    taty = findTat ( y );
//
//    if ( tatx == taty ){
//        return 0 ;
//    }
//
//    if ( dim [ tatx ] < dim [ taty ] ){
//        dim [ taty ] += dim [ tatx ];
//        tat[ tatx ] = taty ;
//    }else{
//        dim [ tatx ] += dim [ taty ];
//        tat [ taty ] = tatx ;
//    }
//    return 1;
//
//
//}
//
//
//bool cmp ( Muchie a , const Muchie b ){
//    return a.cost < b.cost ;
//}
//
//
//void initTat (){
//
//    for ( int i = 1 ; i <= noNodes ; i++ ){
//        tat[ i ] = 0;
//        dim [ i ] = 1 ;
//
//    }
//}
//
//int main(){
//    int j ;
//
//    freopen("zapada.in","r",stdin);
//    freopen("zapada.out","w",stdout);
//
//    scanf("%d %d %d\n",&noNodes ,&noMuc , &noUpgrades );
//
//
//    for ( int i = 0 ; i < noMuc ; i++ ){
//        Muchie temp ;
//        gets( readBuffer );
//        temp.x = temp.y = temp.cost = 0 ;
//        int crLet = 0 ;
//        while ( readBuffer [ crLet ] != ' ' ){
//            temp.x = temp.x * 10 + readBuffer[ crLet++] - '0' ;
//        }
//        crLet++;
//        while ( readBuffer [ crLet ] != ' ' ){
//            temp.y = temp.y * 10 + readBuffer[ crLet++ ] - '0' ;
//        }
//        crLet++;
//        while ( readBuffer [ crLet ]  ){
//            temp.cost = temp.cost * 10 + readBuffer[ crLet++ ] - '0' ;
//        }
//
////        scanf("%d%d%d",&temp.x , &temp.y , &temp.cost );
//        mucInit.push_back( temp );
//    }
//
//    sort ( mucInit.begin() ,mucInit.end() , cmp );
//
//    initTat();
//    int apmCost = 0 ;
//    for ( Muchie crMuc : mucInit ){
//
//        if ( mergeTat( crMuc.x , crMuc.y ) ){
//            apmCost += crMuc.cost ;
//            sol[ noApm++ ] = crMuc ;
//        }
//
//    }
//    printf("%d\n",apmCost);
//
//    int oldApm = apmCost;
//    for ( int i = 0 ; i < noUpgrades ; i++ ){
//        Muchie temp ;
//        scanf("%d%d%d",&temp.x , &temp.y , &temp.cost );
//
//        sol[ noNodes - 1 ] = temp ;
//
//        int ok = 0 ;
//        int mucSwap1 = -1 , mucSwap2 ;
//        apmCost = 0 ;
//        initTat();
//        for ( j = 0 ; j < noNodes - 1 ; j++ ){
//
//            if ( !ok && temp.cost < sol[ j ].cost ){
//                if ( mergeTat( temp.x , temp.y ) ){
//                    apmCost += temp.cost ;
//                    mucSwap1 = j ;
//                }else {
//                    ok = -1 ;
//                    break ;
//                }
//                ok = 1 ;
//            }
//
//            if ( mergeTat( sol [ j ].x , sol [ j ].y ) ){
//                apmCost += sol [ j ].cost ;
//            }else{
//                mucSwap2 = j ;
//            }
//        }
//
//        if ( ok == -1 ){
//            apmCost = oldApm ;
//        }else if ( mucSwap2 != -1 && ok == 1 ){
//            sol[ mucSwap2 ] = temp ;
//
//            for ( int j = mucSwap2 ; j > mucSwap1 ; j-- ){
//                swap( sol [ j ], sol [ j - 1 ] );
//            }
//
//        }
//        oldApm = apmCost ;
//        printf("%d\n",apmCost );
//
//    }
//
//    return 0;
//}