Cod sursa(job #1872038)

Utilizator borcanirobertBorcani Robert borcanirobert Data 7 februarie 2017 21:34:49
Problema Adapost Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.23 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

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

const int MAX = 2*405;
const double Inf = 99999999.;
const double eps = 0.0001;
struct Nod{
    int nod, cost;

    bool operator < ( const Nod& a )
    {
        return cost > a.cost;
    }
};
using VI = vector<int>;
using VF = vector<double>;
vector<int> G[MAX];
VI l, r, u;
vector<pair<double, double>> s, a;
int n, N;
double d[MAX][MAX];
double dmax;
VF dist;
int C[MAX][MAX];
int F[MAX][MAX];
VF Cost;
double rez;

void ReadAndBuildGraph();
bool PairUp( int x );
bool Verif( int ld );
double Minim();
bool Bellman_Ford();

double Abs( double x )
{
    if ( x >= 0 ) return x;
    return -x;
}

int main()
{
    ReadAndBuildGraph();

    double c1 = Minim();
    fout << c1 << ' ';

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( d[i][j + n] - c1 <= eps )
            {
                G[i].push_back(j + n);
                G[j + n].push_back(i);

                C[i][j + n] = 1;
            }

    while ( Bellman_Ford() );

    fout << rez << '\n';

    fin.close();
    fout.close();
    return 0;
}

void ReadAndBuildGraph()
{
    int x, y;
    fin >> n; N = 2*n + 1;
    s = a = vector<pair<double, double>>(n + 1);

    for ( int i = 1; i <= n; ++i )
        fin >> s[i].first >> s[i].second;

    for ( int i = 1; i <= n; ++i )
        fin >> a[i].first >> a[i].second;

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
        {
            d[i][j + n] = sqrt( (a[j].first - s[i].first)*(a[j].first - s[i].first) + (a[j].second - s[i].second)*(a[j].second - s[i].second) );
            d[j + n][i] = -d[i][j + n];
            dist.push_back(d[i][j + n]);
        }
    sort( dist.begin(), dist.end() );

    for ( int i = 1; i <= n; ++i )
    {
        G[0].push_back(i);
        G[i].push_back(0);

        C[0][i] = 1;
    }

    for ( int i = n + 1; i < N; ++i )
    {
        G[i].push_back(N);
        G[N].push_back(i);

        C[i][N] = 1;
    }
}

bool PairUp( int x )
{
    if ( u[x] ) return false;
    u[x] = 1;

    for ( int i = 1; i <= n; ++i )
    {
        if ( !r[i] && d[x][i + n] - dmax <= eps )
        {
            l[x] = i;
            r[i] = x;
            return true;
        }
    }

    for ( int i = 1; i <= n; ++i )
        if ( d[x][i + n] - dmax <= eps )
            if ( PairUp(r[i]) )
            {
                l[x] = i;
                r[i] = x;
                return true;
            }

    return false;
}

bool Verif( int ld )
{
    dmax = dist[ld];
    bool change;

    l = r = VI(n + 1);

    do
    {
        change = false;
        u = VI(n + 1, 0);
        for ( int i = 1; i <= n; ++i )
            if ( !l[i] )
                change |= PairUp(i);
    }while ( change );

    for ( int i = 1; i <= n; ++i )
        if ( !l[i] )
            return false;
    return true;
}

double Minim()
{
    int st = 0, dr = dist.size() - 1, mij;
    double rez;

    while ( st <= dr )
    {
        mij = ( st + dr ) / 2;

        if ( Verif(mij) )
        {
            dr = mij - 1;
            rez = dist[mij];
        }
        else
            st = mij + 1;
    }

    return rez;
}

bool Bellman_Ford()
{
    queue<int> Q;

    Cost = VF(N + 1, Inf);
    VI t(N + 1);
    Cost[0] = 0;
    Q.push(0);

    while ( !Q.empty() )
    {
        int x = Q.front();
        Q.pop();

        for ( const int& y : G[x] )
            if ( C[x][y] - F[x][y] > 0 )
            {
                double c_nou = Cost[x] + d[x][y];
                if ( Cost[y] - c_nou <= eps ) continue;

                Cost[y] = c_nou;
                t[y] = x;
                Q.push(y);
            }
    }

    if ( Abs(Cost[N] - Inf) <= eps )
        return false;

   /* for ( int i = 1; i <= N; ++i )
        cout << i << " : " << Cost[i] << '\n';
    cin.get();  */

    rez += Cost[N];
    for ( int i = N; i != 0; i = t[i] )
    {
        F[t[i]][i]++;
        F[i][t[i]]--;
    }

    return true;
}