Cod sursa(job #931304)

Utilizator rudarelLup Ionut rudarel Data 28 martie 2013 09:59:21
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.98 kb
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#include <math.h>
#include <string.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 ];
double 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, double> > v_final[ DIM<<1 ];
 
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 double bellman_ford() {
 
    int i, nod, fmin;
    vector < pair <int, double> > :: 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 (double)fmin * val[ D ];
    }
 
    return 0;
}
 
int main() {
 
    freopen( "adapost.in", "r", stdin );
    freopen( "adapost.out", "w", stdout );
 
    int i, j, mid, left, right;
    double ok, x_adap, y_adap, distanta;
 
    scanf( "%d", &N );
    for( i = 1; i <= N; ++i )
        scanf( "%lf %lf", &x_sold[ i ], &y_sold[ i ] );
 
    for( i = 1; i <= N; ++i ) {
 
        scanf( "%lf %lf", &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( "%lf %lf", dst_max, sum_min );
 
    return 0;
}