Cod sursa(job #1787798)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 25 octombrie 2016 00:22:04
Problema Adapost Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 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]; 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 n, int &cnt ) {
    if( ma[x] == 1 ) { return false; } ma[x] = 1;
    for( int y = 1; y <= n; y ++ ) { if( adj[x][y] == 1 && r[y] == 0 )         { l[x] = y; r[y] = x; cnt += 1; return true; } }
    for( int y = 1; y <= n; y ++ ) { if( adj[x][y] == 1 && couple(r[y], n, 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) );
    for( int i = 1; i <= n; i ++ ) {
        adj[i].reset(); }
    for( int i = 0; i < edg.size(); i ++ ) {
        if( get<0>(edg[i]) <= k ) {
            adj[ get<1>(edg[i]) ][ get<2>(edg[i]) ] = 1; }
        else
            k = k; }
    int ok, cnt = 0;
    do {
        ok = 0; ma.reset();
        for( int i = 1; i <= n; i ++ ) {
            if( l[i] == 0 && couple(i, n, 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( int i = 0; i < edg.size(); i ++ ) {
        if( get<0>(edg[i]) > fi ) continue;
        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 << fi << " " << ans << endl;

    return 0; }