Cod sursă (job #334475)

#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 ] ;
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[ 0 ][ noApm++ ] = crMuc ;
        }

    }
    printf("%d\n",apmCost);

    bool cr = 0 , old = 1 ;

    for ( int i = 0 ; i < noUpgrades ; i++ , cr = !cr , old = !old ){
        Muchie temp ;
        scanf("%d%d%d",&temp.x , &temp.y , &temp.cost );


        sol[ cr ][ noNodes - 1 ] = temp ;

        int k = noNodes - 1 ;
        while ( k && sol [ cr ][ k ].cost < sol [ cr ][ k - 1 ].cost ){
            swap( sol [ cr ][ k ] , sol [ cr ][ k - 1 ]  );
            k--;
        }
//        sort ( sol[ cr ], sol [ cr ] + noNodes + 1 , cmp );

        noApm = 0 ;
        apmCost = 0 ;
        memset ( tat , -1 , sizeof tat );
        for ( int j = 0 ; j < noNodes ; j++ ){
            Muchie crMuc = sol [ cr ][ j ];

            if ( mergeTat( crMuc.x , crMuc.y ) ){
                apmCost += crMuc.cost ;
                sol[ old ][ noApm++ ] = crMuc ;
            }
        }
        printf("%d\n",apmCost );

    }

    return 0;
}