Cod sursa(job #1787779)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 octombrie 2016 23:52:16
Problema Adapost Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <bits/stdc++.h>
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;
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, int k ) {
    fill( g + 1, g + n + 1, vector<int>(0) );
    fill( l + 1, l + n + 1, 0 ); fill( r + 1, r + n + 1, 0 );
    for( int i = 0; i <= k; i ++ ) {
        int x = get<1>(edg[i]), y = get<2>(edg[i]);
        g[ get<1>(edg[i]) ].push_back( get<2>(edg[i]) ); }
    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; 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 ++ ) {
            edg.push_back( make_tuple( hypot( fabs(x - pts[j].first ), fabs(y - pts[j].second) ), j + 1, i + 1 ) ); } }
    sort( edg.begin(), edg.end(), cmp );

    int st = 0, fi = n * n - 1, mid;
    while( st <= fi ) {
        mid = st + ( fi - st ) / 2;
        ( solve(n, mid) ) ? ( fi = mid - 1 ) : ( st = mid + 1 ); }
    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( int i = 0; i <= st; i ++ ) {
        double d = get<0>(edg[i]); int x = get<1>(edg[i]), y = get<2>(edg[i]);
        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 << get<0>(edg[st]) << " " << ans << endl;

    return 0; }