Cod sursa(job #403326)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 24 februarie 2010 20:45:20
Problema Adapost Scor 41
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.89 kb
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;

#define DIM 405
#define INF 0x3f3f3f3f

int N, S, D;
int cnt, l[ DIM ], r[ DIM ], t[ DIM<<1 ], cap[ DIM<<1 ][ DIM<<1 ], flx[ DIM<<1 ][ DIM<<1 ];
float dst_max, sum_min, val[ DIM<<1 ], dst_sort[ DIM*DIM ], x_sold[ DIM ], y_sold[ DIM ], dst[ DIM ][ DIM ];
bitset <DIM<<1> f;
vector <int> v[ DIM ];
vector < pair <int, float> > v_final[ DIM ];

struct cmp {

    bool operator()( const int &a, const int &b ) {

        return val[ a ] > val[ b ];
    }
};
priority_queue < int, vector <int>, cmp > heap;

inline int pair_up( const int &nod ) {

    vector <int> :: iterator it;

    if( f[ nod ] )
        return 0;

    f[ nod ] = 1;
    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
        if( !r[ *it ] ) {

            l[ nod ] = *it;
            r[ *it ] = nod;

            return 1;
        }
    for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
        if( pair_up( r[ *it ] ) ) {

            l[ nod ] = *it;
            r[ *it ] = nod;

            return 1;
        }

    return 0;
}

inline int cuplaj_max() {

    int i, ok, cuplaj;

    cuplaj = 0;
    memset( l, 0, sizeof( l ) );
    memset( r, 0, sizeof( r ) );

    do {

        ok = 0;
        f.reset();
        for( i = 1; i <= N; ++i )
            if( !l[ i ] && pair_up( i ) ) {

                ++cuplaj;
                ok = 1;
            }
    }
    while( ok );

    if( cuplaj == N )
        return 1;

    return 0;
}

inline float bellman_ford() {

    int i, nod, fmin;
    vector < pair <int, float> > :: iterator it;

    f.reset();
    memset( t, 0, sizeof( t ) );
    for( i = 1; i <= 2*N+2; ++i )
        val[ i ] = INF;

    heap.push( S );
    f[ S ] = 1;
    val[ S ] = 0;
    while( !heap.empty() ) {

        nod = heap.top();
        heap.pop();
        f[ nod ] = 0;
        for( it = v_final[ nod ].begin(); it != v_final[ nod ].end(); ++it )
            if( cap[ nod ][ it->first ] > flx[ nod ][ it->first ] && val[ nod ] + it->second < val[ it->first ] ) {

                val[ it->first ] = val[ nod ] + it->second;
                t[ it->first ] = nod;
                if( !f[ it->first ] ) {

                    heap.push( it->first );
                    f[ it->first ] = 1;
                }
            }
    }
    if( val[ D ] != INF ) {

        fmin = INF;
        for( nod = D; nod != S; nod = t[ nod ] )
            fmin = min( fmin, cap[ t[ nod ] ][ nod ] - flx[ t[ nod ] ][ nod ] );
        for( nod = D; nod != S; nod = t[ nod ] ) {

            flx[ t[ nod ] ][ nod ] += fmin;
            flx[ nod ][ t[ nod ] ] -= fmin;
        }

        return (float)fmin * val[ D ];
    }

    return 0;
}

int main() {

    freopen( "adapost.in", "r", stdin );
    freopen( "adapost.out", "w", stdout );

    int i, j, mid, left, right;
    float ok, x_adap, y_adap, distanta;

    scanf( "%d", &N );
    for( i = 1; i <= N; ++i )
        scanf( "%f %f", &x_sold[ i ], &y_sold[ i ] );

    for( i = 1; i <= N; ++i ) {

        scanf( "%f %f", &x_adap, &y_adap );
        for( j = 1; j <= N; ++j ) {

            distanta = sqrt( ( x_sold[ j ] - x_adap ) * ( x_sold[ j ] - x_adap ) + ( y_sold[ j ] - y_adap ) * ( y_sold[ j ] - y_adap ) );
            dst_sort[ ++cnt ] = distanta;
            dst[ j ][ i ] = distanta;
        }
    }

    sort( dst_sort+1, dst_sort+cnt+1 );

    left = 1;
    right = cnt;
    while( left <= right ) {

        mid = (left+right) / 2;

        for( i = 1; i <= N; ++i )
            v[ i ].clear();

        for( i = 1; i <= N; ++i )
            for( j = 1; j <= N; ++j )
                if( dst[ i ][ j ] <= dst_sort[ mid ] )
                    v[ i ].push_back( j );

        if( cuplaj_max() ) {

            dst_max = dst_sort[ mid ];
            right = mid-1;
        }
        else
            left = mid+1;
    }

    for( i = 1; i <= N; ++i )
        v[ i ].clear();

    for( i = 1; i <= N; ++i )
        for( j = 1; j <= N; ++j )
            if( dst[ i ][ j ] <= dst_max ) {

                v_final[ i+1 ].push_back( make_pair( j+N+1, dst[ i ][ j ] ) );
                v_final[ j+N+1 ].push_back( make_pair( i+1, -dst[ i ][ j ] ) );
                cap[ i+1 ][ j+N+1 ] = 1;
            }
    S = 1;
    for( i = 2; i <= N+1; ++i ) {

        v_final[ S ].push_back( make_pair( i, 0 ) );
        v_final[ i ].push_back( make_pair( S, 0 ) );
        cap[ S ][ i ] = 1;
    }
    D = 2*N+2;
    for( i = N+2; i <= 2*N+1; ++i ) {

        v_final[ i ].push_back( make_pair( D, 0 ) );
        v_final[ D ].push_back( make_pair( i, 0 ) );
        cap[ i ][ D ] = 1;
    }

    do {

        ok = bellman_ford();
        sum_min += ok;
    }
    while( ok );

    printf( "%f %f", dst_max, sum_min );

    return 0;
}