Cod sursa(job #1164361)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 2 aprilie 2014 00:10:08
Problema Adapost Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

const int Nmax = 404;
const double inf = 1e9;
const double EPS = 1e-5;

struct NODE
{
    int nod;
};

#define Point pair<double,double>
#define x first
#define y second

vector <int> GG[Nmax];
vector <int> G[2 * Nmax];
priority_queue <int> MinHeap;
int C[2 * Nmax][2 * Nmax];
int F[2 * Nmax][2 * Nmax];
double Cost[2 * Nmax][2 * Nmax];
Point soldier[Nmax], shelter[Nmax];
double D[Nmax][Nmax];
int use[Nmax], st[Nmax], dr[Nmax];
int tata[2 * Nmax], coada[2 * Nmax], in_q[2 * Nmax];
double dist[2 * Nmax];
double v[Nmax * Nmax];

int N;
int source, sink, DIM;

double sq( double a )
{
    return a * a;
}

double euclid_dist( Point A, Point B )
{
    return sqrt( sq( A.x - B.x ) + sq( A.y - B.y ) );
}

void erase_graph()
{
    for ( int i = 1; i <= N; ++i )
            GG[i].clear();

    memset( use, 0, sizeof ( use ) );
    memset( st, 0, sizeof( st ) );
    memset( dr, 0, sizeof( dr ) );
}

void make_graph( double x )
{
    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    if ( D[i][j] <= x )
                            GG[i].push_back( j );
}

int pairup( int nod )
{
    if ( use[nod] )
            return 0;

    use[nod] = 1;

    for ( auto x: GG[nod] )
            if ( !dr[x] )
            {
                st[nod] = x;
                dr[x] = nod;
                return 1;
            }

    for ( auto x: GG[nod] )
            if ( pairup( dr[x] ) )
            {
                st[nod] = x;
                dr[x] = nod;
                return 1;
            }

    return 0;
}

int HopcroftKarp()
{
    for ( int change = 1; change; )
    {
        change = 0;
        memset( use, 0, sizeof( use ) );

        for ( int i = 1; i <= N; ++i )
                if ( !st[i] )
                        change |= pairup( i );
    }

    int match = 0;

    for ( int i = 1; i <= N; ++i )
            match += ( st[i] > 0 );

    return match;
}

int valid( double x )
{
    erase_graph();
    make_graph( x );

    return HopcroftKarp();
}

void add_edge( int x, int y, int cap, double cost )
{
    G[x].push_back( y );
    G[y].push_back( x );

    C[x][y] = cap;
    Cost[x][y] = +cost;
    Cost[y][x] = -cost;
}

void build_network( double x )
{
    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    if ( D[i][j] <= x )
                    {
                        add_edge( i, j + N, 1, D[i][j] );
                    }

    source = 0;
    sink = 2 * N + 1;
    DIM = 2 * N + 1;

    for ( int i = 1; i <= N; ++i )
            add_edge( source, i, 1, 0 );

    for ( int i = 1; i <= N; ++i )
            add_edge( i + N, sink, 1, 0 );
}

void BellmanFord( int S, int D )
{
    for ( int i = 0; i <= DIM; ++i )
    {
        dist[i] = inf;
        in_q[i] = 0;
    }

    int st, dr;
    coada[st = dr = 1] = S;
    in_q[S] = 1;
    dist[S] = 0;

    while ( st <= dr )
    {
        int nod = coada[ st++ ];

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                dist[x] = dist[nod] + Cost[nod][x];

                if ( !in_q[x] )
                {
                    in_q[x] = 1;
                    coada[ ++dr ] = x;
                }
            }
        }
    }
}

void init( int S, int D )
{
    for ( int i = 0; i <= DIM; ++i )
    {
        for ( auto x: G[i] )
        {
            if ( dist[i] != inf && dist[x] != inf )
            {
                Cost[i][x] += dist[i] - dist[x];
            }
        }
    }

    for ( int i = 0; i <= DIM; ++i )
    {
        dist[i] = inf;
        tata[i] = 0;
        in_q[i] = 0;
    }

    dist[S] = 0;
}

int Dijkstra( int S, int D )
{
    init( S, D );
    MinHeap.push( S );
    in_q[S] = 1;

    while ( MinHeap.size() )
    {
        int nod = MinHeap.top();
        in_q[nod] = 0;

        MinHeap.pop();

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                dist[x] = dist[nod] + Cost[nod][x];
                tata[x] = nod;

                if ( !in_q[x] )
                {
                    in_q[x] = 1;
                    MinHeap.push( x );
                }
            }
        }
    }

    return ( dist[D] < inf );
}

double EdmondsKarp( int S, int D )
{
    int flow = 0, fmin;
    double flowCost = 0, distD = dist[D];

    while ( Dijkstra( S, D ) )
    {
        fmin = inf;

        for ( int nod = D; nod != S; nod = tata[nod] )
                fmin = min( fmin, C[ tata[nod] ][nod] - F[ tata[nod] ][nod] );

        for ( int nod = D; nod != S; nod = tata[nod] )
        {
            F[ tata[nod] ][nod] += fmin;
            F[nod][ tata[nod] ] -= fmin;
        }

        flow += fmin;
        distD += dist[D];
        flowCost += 1.0 * distD * fmin;
    }


    return flowCost;
}

queue <int> Q;
int inQ[Nmax];

inline bool bellman_ford ( int S, int D ) {

    Q.push(S); inQ[S] = 1;

    for ( int i = 0; i <= DIM; ++i ){
        dist[i] = inf;
    }
    dist[S] = 0;

    while ( !Q.empty() ){
        int nod = Q.front(); Q.pop(); inQ[nod] = 0;

        for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
            int nodvcn = (*itt);
            if ( dist[nodvcn] > dist[nod] + Cost[nod][nodvcn] && F[nod][nodvcn] < C[nod][nodvcn] ){
                dist[nodvcn] = dist[nod] + Cost[nod][nodvcn]; tata[nodvcn] = nod;
                if ( !inQ[nodvcn] ){
                    Q.push(nodvcn);
                    inQ[nodvcn] = 1;
                }
            }
        }
    }

    return dist[D] != inf;
}

inline double flux ( int S, int D ) {
    double flow_cost = 0;

    while ( bellman_ford( S, D ) ){

        int nod;
        for ( nod = D ; nod != S; nod = tata[nod] ){
            ++F[tata[nod]][nod];
            --F[nod][tata[nod]];
        }

        flow_cost += dist[D];
    }

    return flow_cost;
}

int main()
{
    ifstream f("adapost.in");
    ofstream g("adapost.out");

    f >> N;

    for ( int i = 1; i <= N; ++i )
            f >> soldier[i].x >> soldier[i].y;

    for ( int i = 1; i <= N; ++i )
            f >> shelter[i].x >> shelter[i].y;

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    D[i][j] = euclid_dist( soldier[i], shelter[j] );

    double sol = 0;
    double step;

    for ( step = 1; step <= 1000; step *= 2 );

    for ( ; step > 0.000001; step *= 0.5 )
            if ( valid( sol + step ) < N )
                    sol += step;

    sol += EPS;

    build_network( sol );

    g << fixed << setprecision( 5 );
    g << sol << " " << flux( source, sink ) << "\n";

    return 0;
}