Cod sursă (job #334497)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.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 [ 2 ][ N ] ;
Muchie sol [ N ] ;
int noApm ;
int tat [ 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 ( -tat [ tatx ] < -tat [ taty ] ){
        tat [ taty ] += tat [ tatx ];
        tat[ tatx ] = taty ;
    }else{
        tat [ tatx ] += tat [ taty ];
        tat [ taty ] = tatx ;
    }
    return 1;


}


bool cmp ( Muchie a , Muchie b ){
    return a.cost < b.cost ;
}

int main(){

    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 );

    memset ( tat , -1 , sizeof tat );

    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 ;
        memset ( tat , -1 , sizeof tat );
        for ( int 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;
}