Cod sursă (job #570075)

#include <algorithm>
#include <stdio.h>

struct Andrei{
    int a, b, cost;
}v[ 101001 ], element;
int t[ 10000 ], n, m;

bool cmp( Andrei A, Andrei B ){
    return ( A.cost < B.cost );
}

int Kruskal(){
    int s = 0;
    for( int i = 1; i <= n; i++ )
        t[ i ] = i;
    int cnt = 0;
    for( int i = 0; i < m && cnt < n; i++ )
        if( t[ v[ i ].a ] != t[ v[ i ].b ] ){
            s += v[ i ].cost;
            int aa = t[ v[ i ].a ];
            int bb = t[ v[ i ].b ];
            for( int j = 1; j <= n; j++ )
                if( t[ j ] == bb )
                    t[ j ] = aa;
        }
    return s;
}

int main()
{
    int k, i;
    FILE *fin = fopen( "zapada.in", "r" );
    fscanf( fin, "%d %d %d", &n, &m, &k );
    for( i = 0; i < m; i++ )
        fscanf( fin, "%d %d %d", &v[ i ].a, &v[ i ].b, &v[ i ].cost );
    FILE *fout = fopen( "zapada.out", "w" );
    std::sort( v, v + m, cmp );
    fprintf( fout, "%d\n", Kruskal() );
    while( k-- ){
       //fscanf( fin, "%d %d %d", &element.a, &element.b, &element.cost );
        fscanf( fin, "%d %d %d", &v[ m ].a, &v[ m ].b, &v[ m ].cost );
        ++m;
        std::sort( v, v + m, cmp );
        /*int poz = 0;
        while( v[ poz++ ].cost < element.cost );
        for( i = ++m; i > poz; i-- )
            v[ i ] = v[ i - 1 ];
        v[ poz ] = element;*/
        fprintf( fout, "%d\n", Kruskal() );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}