Pagini recente » Cod sursa (job #984897) | Cod sursa (job #508148) | Cod sursa (job #303084) | Cod sursa (job #2612) | Cod sursa (job #402370)
Cod sursa(job #402370)
#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 D[ DIM*DIM ], X[ DIM ], Y[ DIM ];
float dist, sum_dist, cost_cuplaj, val[ DIM<<1 ], cst[ DIM<<1 ][ DIM<<1 ];
bitset <DIM<<1> f;
queue <int> q;
inline float bellman_ford( const float &dist_max ) {
int i, nod, fmin;
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 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;
}
printf( "%f %f", dist, sum_dist );
return 0;
}