Cod sursă (job #334507)

#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])
        tat[tatx] = taty, dim[tatx] += dim[taty];
    else
        tat[taty] = tatx, dim[taty] += dim[tatx];
//    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;
}