Cod sursa(job #402385)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 23 februarie 2010 20:29:13
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.23 kb
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
using namespace std;

#define DIM 405
#define INF 0x3f3f3f3f

int N;
int cnt, surs, dest, cuplaj, t[ DIM<<1 ], cap[ DIM<<1 ][ DIM<<1 ], flx[ DIM<<1 ][ DIM<<1 ];
float dist, sum_dist, cost_cuplaj, cst[ DIM<<1 ][ DIM<<1 ];

inline float bellman_ford( const float &dist_max ) {

    int i, nod, fmin;
    float val[ DIM<<1 ];
    bitset <DIM<<1> f;
    queue <int> q;

    f.reset();
    for( i = 1; i <= 2*N+2; ++i )
        val[ i ] = INF;

    val[ surs ] = 0;
    for( q.push( surs ); !q.empty(); q.pop() ) {

        nod = q.front();
        f[ nod ] = 0;

        if( nod == surs ) {

            for( i = 2; i <= N+1; ++i )
                if( cap[ nod ][ i ] > flx[ nod ][ i ] && cst[ nod ][ i ] <= dist_max && val[ nod ] + cst[ nod ][ i ] < val[ i ] ) {

                    val[ i ] = val[ nod ] + cst[ nod ][ i ];
                    t[ i ] = nod;
                    if( !f[ i ] ) {

                        q.push( i );
                        f[ i ] = 1;
                    }
                }
        }

        else if( 2 <= nod && nod <= N+1 ) {

            for( i = N+2; i <= 2*N+1; ++i )
                if( cap[ nod ][ i ] > flx[ nod ][ i ] && cst[ nod ][ i ] <= dist_max && val[ nod ] + cst[ nod ][ i ] < val[ i ] ) {

                    val[ i ] = val[ nod ] + cst[ nod ][ i ];
                    t[ i ] = nod;
                    if( !f[ i ] ) {

                        q.push( i );
                        f[ i ] = 1;
                    }
                }
        }

        else if( N+2 <= nod && nod <= 2*N+1 ) {

            for( i = 2; i <= N+1; ++i )
                if( cap[ nod ][ i ] > flx[ nod ][ i ] && cst[ nod ][ i ] <= dist_max && val[ nod ] + cst[ nod ][ i ] < val[ i ] ) {

                    val[ i ] = val[ nod ] + cst[ nod ][ i ];
                    t[ i ] = nod;
                    if( !f[ i ] ) {

                        q.push( i );
                        f[ i ] = 1;
                    }
                }
            if( cap[ nod ][ dest ] > flx[ nod ][ dest ] && cst[ nod ][ dest ] <= dist_max && val[ nod ] + cst[ nod ][ dest ] < val[ dest ] ) {

                    val[ dest ] = val[ nod ] + cst[ nod ][ dest ];
                    t[ dest ] = nod;
                    if( !f[ dest ] ) {

                        q.push( dest );
                        f[ dest ] = 1;
                    }
                }
        }

        else if( nod == dest ) {

            for( i = N+2; i <= 2*N+1; ++i )
                if( cap[ nod ][ i ] > flx[ nod ][ i ] && cst[ nod ][ i ] <= dist_max && val[ nod ] + cst[ nod ][ i ] < val[ i ] ) {

                    val[ i ] = val[ nod ] + cst[ nod ][ i ];
                    t[ i ] = nod;
                    if( !f[ i ] ) {

                        q.push( i );
                        f[ i ] = 1;
                    }
                }
        }
    }

    if( val[ dest ] != INF ) {

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

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

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

    return 0;
}

inline int cuplaj_mcm( const float &dist_max ) {

    int i, j;
    float ok;

    cuplaj = 0;
    cost_cuplaj = 0;
    memset( flx, 0, sizeof( flx ) );

    do {

        ok = bellman_ford( dist_max );
        cost_cuplaj += ok;
    }
    while( ok );

    for( i = 2; i <= 2*N+1; ++i )
        for( j = 2; j <= 2*N+1; ++j )
            if( cap[ i ][ j ] && flx[ i ][ j ] ) {

                ++cuplaj;
                break;
            }
    if( cuplaj == N )
        return 1;

    return 0;
}

int main() {

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

    int i, j, mid, left, right;
    float D[ DIM*DIM ], X[ DIM ], Y[ DIM ];
    float x_adap, y_adap;

    scanf( "%d", &N );
    for( i = 1; i <= N; ++i )
        scanf( "%f %f", &X[ i ], &Y[ i ] );
    for( i = 1; i <= N; ++i ) {

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

            cap[ j+1 ][ i+N+1 ] = 1;
            D[ ++cnt ] = (float)sqrt( ( X[ j ] - x_adap ) * ( X[ j ] - x_adap ) + ( Y[ j ] - y_adap ) * ( Y[ j ] - y_adap ) );
            cst[ j+1 ][ i+N+1 ] = D[ cnt ];
            cst[ i+N+1 ][ j+1 ] = -D[ cnt ];
        }
    }

    surs = 1;
    for( i = 2; i <= N+1; ++i )
        cap[ surs ][ i ] = 1;
    dest = 2*N+2;
    for( i = N+2; i <= 2*N+1; ++i )
        cap[ i ][ dest ] = 1;

    sort( D+1, D+N*N+1 );
//    left = 1;
//    right = N*N;
//    while( left <= right ) {
//
//        mid = (left+right) / 2;
//        if( cuplaj_mcm( D[ mid ] ) ) {
//
//            dist = D[ mid ];
//            sum_dist = cost_cuplaj;
//            right = mid-1;
//        }
//        else
//            left = mid+1;
//    }

    if( cuplaj_mcm( D[ N*N ] ) )
        printf( "%f %f", D[ N*N ], cost_cuplaj );

//    printf( "%f %f", dist, sum_dist );

    return 0;
}