Cod sursa(job #2392448)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 29 martie 2019 23:55:41
Problema Adapost Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.56 kb
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
using namespace std ;
const int NR = 850 , oo = 1000000005 ;
ifstream in ("adapost.in") ;
ofstream out ("adapost.out") ;
vector < int > v [ NR ] ;
vector < double > d ( NR ) , edge ;
int n , x , t [ NR ] , st , dr , mid ;
double cost [ NR ][ NR ] , cap [ NR ][ NR ] , limit , best , maxedge , ans = 1000000005 ;
pair < double , double > p [ NR ] , ad [ NR ] ;
double sol ;
bool inq [ NR ] ;
struct cmp  {
    inline bool operator() ( const int i , const int j )    {
    return d [ i ] > d [ j ] ;
    }
};
priority_queue < int , vector < int > , cmp > q ;
bool dijkstra (  )  {
int nod , i ;
    for ( i = 1 ; i <= 2 * n + 1 ; ++ i )   d [ i ] = oo ;
    d [ 0 ] = 0 ;
    q.push( 0 ) ;
    while ( !q.empty() )    {

        nod = q.top() ;
        q.pop() ;
        inq [ nod ] = 0 ;
        for ( vector < int > :: iterator it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )
            if ( cap [ nod ][ *it ] )   {
            if (  d [ nod ] + cost [ nod ][ *it ] >= 0 && d [ nod ] + cost [ nod ][ *it ] < d [ *it ] && ( abs ( cost [ nod ][ *it ] ) <= limit || !cost [ nod ][ *it ] ) )    {
                 d [ *it ] = d [ nod ] + cost [ nod ][ *it ] ;
                q.push( *it )  ;
                t [ *it ] = nod ;
              }
            }
    }
    if ( d [ n << 1 | 1 ] == oo )  return 0 ;
    nod = 2*n + 1 ;
    while ( nod )   {
        cap [ t [ nod ] ][ nod ] = 0 ;
        cap [ nod ][ t [ nod ] ] = 1 ;
        nod = t [ nod ] ;
    }
    maxedge = max ( maxedge , d[ n << 1 | 1 ] ) ;
    sol += d[ n << 1 | 1 ] ;
    return 1 ;
}
int main () {
    int i , j ;
    in >> n ;

    for ( i = 1 ; i <= n ; ++ i )   {
    in >> p [ i ].f >> p [ i ].s ;
    }
    for ( i = 1 ; i <= n ; ++ i )   {
    in >> ad [ i ].f >> ad [ i ].s ;
    }

    for ( i = 1 ; i <= n ; ++ i )
    for ( j = 1 ; j <= n ; ++ j )   {

        cost [ i ][ j + n ] = sqrt ( ( ad [ i ].f - p [ j ].f ) * ( ad [ i ].f - p [ j ].f ) + ( ad [ i ].s - p [ j ].s ) * ( ad [ i ].s - p [ j ].s ) ) ;
        cap [ i ][ j + n ] = 1 ;
        edge.pb ( cost [ i ][ j + n ] ) ;
        cost [ j + n ][ i ] = - cost [ i ][ j + n ] ;
        v [ i ].pb ( j + n ) ;
        v [ j + n ].pb ( i ) ;
    }

    for ( i = 1 ; i <= n ; ++ i )   {
        cap [ 0 ][ i ] = 1 ;
        v [ 0 ].pb ( i ) ;
        v [ i ].pb ( 0 ) ;
        cap [ i + n ][ n << 1 | 1 ] = 1 ;
        v [ i + n ].pb ( n << 1 | 1 ) ;
        v [ n << 1 | 1 ].pb ( i + n ) ;
    }

    sort ( edge.begin() , edge.end() ) ;

    limit = edge [ edge.size() - 1 ] ;
    while ( dijkstra() ) ;
    ans = min ( maxedge , ans ) ;
    best = sol ;
    st = 0 ;
    dr = edge.size() - 1 ;

    while ( st < dr )   {


   if ( dr == st + 1 ) {

                sol = 0 ;
                mid = dr ;
                limit = edge [ mid ] ;
                for ( i = 1 ; i <= n ; ++ i )
                for ( j = 1 ; j <= n ; ++ j )
                cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
                for ( i = 1 ; i <= n ; ++ i )   cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
                maxedge =  0 ;
                while ( dijkstra() ) ;
                if ( sol == best )  ans = min ( edge [ mid ] , ans ) ;

                sol = 0 ;
                mid = st ;
                limit = edge [ mid ] ;
                for ( i = 1 ; i <= n ; ++ i )
                for ( j = 1 ; j <= n ; ++ j )
                cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
                for ( i = 1 ; i <= n ; ++ i )   cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
                maxedge =  0 ;
                while ( dijkstra() ) ;
                if ( sol == best )  ans = min ( edge [ mid ] , ans ) ;

                break ;
            }

        mid = ( st + dr ) >> 1 ;
        sol = 0 ;
        limit = edge [ mid ] ;
        for ( i = 1 ; i <= n ; ++ i )
        for ( j = 1 ; j <= n ; ++ j )
        cap [ i ][ j + n ] = 1 , cap [ j + n ][ i ] = 0 ;
        for ( i = 1 ; i <= n ; ++ i )   cap [ 0 ][ i ] = 1 , cap [ i ][ 0 ] = 0 , cap [ i + n ][ 2 * n + 1 ] = 1 , cap [ 2 * n + 1 ][ i + n ] = 0 ;
        maxedge =  0 ;
        while ( dijkstra() ) ;
        if ( sol == best )  ans = min ( edge [ mid ] , ans ) , dr = mid - 1 ;
        else                st = mid + 1 ;
    }
    out << fixed << setprecision( 7 ) << ans << ' ' << best << '\n' ;
}