Pagini recente » Cod sursa (job #2857205) | Cod sursa (job #2148829) | Cod sursa (job #1627775) | Cod sursa (job #2328115) | Cod sursa (job #402385)
Cod sursa(job #402385)
#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;
}