Cod sursa(job #1787802)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 25 octombrie 2016 00:26:30
Problema Adapost Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <vector>
#include <deque>
#include <tuple>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;

ifstream in ( "adapost.in"  );
ofstream out( "adapost.out" );

const int DIM = 8e3 + 5;
const int INF = 0x3f3f3f3f;

vector< pair<double, double> > pts; vector< tuple<double, int, int> > edg; vector<int> e[DIM], g[DIM];
bitset<DIM> ma, adj[DIM]; double dst[DIM][DIM], dp[DIM]; int cap[DIM][DIM], flo[DIM][DIM], l[DIM], r[DIM], fth[DIM];

bool cmp( tuple<double, int, int> t1, tuple<double, int, int> t2 ) {
    return get<0>(t1) < get<0>(t2); }

bool couple( int x, int &cnt ) {
    if( ma[x] == 1 ) { return false; } ma[x] = 1;
    for( auto y : g[x] ) { if( r[y] == 0 )         { l[x] = y; r[y] = x; cnt += 1; return true; } }
    for( auto y : g[x] ) { if( couple(r[y], cnt) ) { l[x] = y; r[y] = x; cnt += 0; return true; } }
    return false; }

bool solve( int n, double k ) {
    memset( l, 0, sizeof(l) ); memset( r, 0, sizeof(r) );
    fill( g + 1, g + n + 1, vector<int>(0) );
    for( auto ed : edg ) {
        if( get<0>(ed) <= k ) {
            g[ get<1>(ed) ].push_back( get<2>(ed) ); } }
    for( int i = 1; i <= n; i ++ ) {
        sort( g[i].begin(), g[i].end() );
        g[i].erase( unique( g[i].begin(), g[i].end() ), g[i].end() ); }
    int ok, cnt = 0;
    do {
        ok = 0; ma.reset();
        for( int i = 1; i <= n; i ++ ) {
            if( l[i] == 0 && couple(i, cnt) ) ok = 1; }
    } while( ok == 1 );
    return ( n == cnt ); }

bool bfs( int st, int fi ) {
    fill( fth + 1, fth + fi + 1, 0 ); fill( dp + 1, dp + fi + 1, INT_MAX );
    deque<int> que; ma.reset(); ma[st] = 1; que.push_back( st ); bool ok = 0;
    while( que.empty() == 0 ) {
        int x = que.front(); que.pop_front(); ma[x] = 0;
        for( auto y : e[x] ) {
            if( flo[x][y] < cap[x][y] && dp[y] > dp[x] + dst[x][y] ) {
                dp[y] = dp[x] + dst[x][y]; fth[y] = x;
                if( ma[y] == 0 ) {
                    ma[y] = 1; que.push_back( y );
                    if( y == fi ) ok = 1; } } } }
    return ok;
}

int main( int argc, const char *argv[] ) {

    int n; double dmax = 0; in >> n;
    for( int i = 0; i < n; i ++ ) {
        double x, y; in >> x >> y;
        pts.push_back( make_pair(x, y) ); }
    for( int i = 0; i < n; i ++ ) {
        double x, y; in >> x >> y;
        for( int j = 0; j < n; j ++ ) {
            double dis = hypot( fabs(x - pts[j].first ), fabs(y - pts[j].second) );
            edg.push_back( make_tuple( dis, j + 1, i + 1 ) ); dmax = max( dmax, dis ); } }

    double st = 0, fi = dmax, mid;
    for( int i = 1; i <= 23; i ++ ) {
        mid = st + ( fi - st ) / 2;
        ( solve(n, mid) ) ? ( fi = mid ) : ( st = mid ); }
    for( int i = 1; i <= n; i ++ ) {
        cap[0][i] = 1; cap[i + n][n * 2 + 1] = 1;
        e[0].push_back( i ); e[i + n].push_back( n * 2 + 1 );
        e[i].push_back( 0 ); e[n * 2 + 1].push_back( i + n ); }
    for( auto ed : edg ) {
        if( get<0>(ed) > fi ) continue;
        double d = get<0>(ed); int x = get<1>(ed), y = get<2>(ed);
        cap[x][y + n] = 1; dst[x][y + n] = d; dst[y + n][x] = -d;
        e[x].push_back( y + n ); e[y + n].push_back( x ); }

    double ans = 0;
    while( bfs(0, n * 2 + 1) ) {
        int minim = INT_MAX;
        for( int x = n * 2 + 1; x != 0; x = fth[x] )
            minim = min( minim, cap[ fth[x] ][x] - flo[ fth[x] ][x] );
        for( int x = n * 2 + 1; x != 0; x = fth[x] ) {
            ans += minim * 1.0 * dst[ fth[x] ][x]; flo[ fth[x] ][x] += minim; flo[x][ fth[x] ] -= minim; } }
    out << setprecision(5) << fixed << fi << " " << ans << endl;

    return 0; }