Cod sursa(job #934467)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 30 martie 2013 17:48:57
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

#define Nmax 250005
#define Mmax 500005

struct S{

    int x;
    int y;
    int c;

} A[Mmax], Aux[Nmax];

int RANG[Nmax], TATA[Nmax];

int N, M, RES, X, Y;

void MergeSort( int st, int dr ){

    int m = ( st + dr ) / 2;

    if ( st == dr )
        return;

    MergeSort( st, m );
    MergeSort( m + 1, dr );

    for ( int i = st, j = m + 1, k = st; i <= m || j <= dr; )
        if ( j > dr || ( i <= m && A[i].c <= A[j].c ) )
            Aux[k++] = A[i++];
        else
            Aux[k++] = A[j++];

    for ( int k = st; k <= dr; k++ )
        A[k] = Aux[k];
}

int gaseste( int x ){

    int R, y;

    for( R = x; TATA[R] != R; R = TATA[R] );

    for( ; TATA[x] != x; ){

        y = TATA[x];
        TATA[x] = R;
        x = y;
    }

    return R;
}

void uneste ( int x, int y ){

    if ( RANG[x] > RANG[y] )
        TATA[y] = x;
    else
        TATA[x] = y;

    if ( RANG[x] == RANG[y] )
        RANG[y]++;
}

void init(){

    for ( int i = 1; i <= N; i++ )
        TATA[i] = i,
        RANG[i] = 1;
}

void Kruskal(){

    for ( int i = 1; i <= M; i++ ){

        int a = gaseste ( A[i].x );
        int b = gaseste ( A[i].y );

        if ( a != b )
            uneste ( a, b );

        if ( gaseste( X ) == gaseste ( Y ) ){

            RES = A[i].c;

            return;
        }
    }
}

void citire(){

    ifstream f("pscnv.in");

    f >> N >> M >> X >> Y;

    for ( int i = 1; i <= M; i++ )
        f >> A[i].x >> A[i].y >> A[i].c;

    f.close();
}

void afis(){

    ofstream g("pscnv.out");

    g << RES << "\n";

    g.close();
}

int main(){

    citire();
    MergeSort( 1, M );
    init();
    Kruskal();
    afis();

    return 0;
}