Cod sursa(job #989816)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 26 august 2013 15:49:37
Problema Traseu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define x first
#define y second
#define newn a[x][i]
#define newnn g[x][i]

using namespace std;

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

const int N = 410;
const int M = N * 2;
const int oo = 0x3f3f3f3f;
const double eps = 0.0001;

int s, d, n, nn, A[N], B[N], c[M][M], t[M];
typedef pair <double, double> pct;
double sol1, sol2, cst[N][N], cost[M][M], dist[M];
pct st[N], dr[N];
vector <int> a[N], g[M];
vector <bool> viz(N), inq(M);
queue <int> q;

double Dist(pct a, pct b)
{
    return sqrt((b.x-a.x) * (b.x-a.x) + (b.y-a.y) * (b.y-a.y));
}

void Read()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>st[i].x>>st[i].y;
    for(int i=1; i<=n; i++)
        fin>>dr[i].x>>dr[i].y;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cst[i][j] = Dist(st[i], dr[j]);
}

void Initialise(double lmax)
{
    for(int i=1; i<=n; i++)
        a[i].clear();
    for(int i=1; i<=n; i++)
        A[i] = B[i] = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(cst[i][j] < lmax)
                a[i].push_back(j);
}

bool Pair(int x)
{
    if(viz[x]) return 0;
    for(unsigned i=0; i<a[x].size(); i++)
        if(!B[newn])
        {
            A[x] = newn; B[newn] = x;
            return 1;
        }
    for(unsigned i=0; i<a[x].size(); i++)
        if(Pair(B[newn]))
        {
            A[x] = newn; B[newn] = x;
            return 1;
        }
    return 0;
}

bool OK(double lmax)
{
    Initialise(lmax);
    bool ok = 1; int nr = 0;
    while(ok)
    {
        ok = 0;
        viz.assign(n+1, 0);
        for(int i=1; i<=n; i++)
            if(!A[i] && Pair(i)) ok = 1, nr++;
    }
    return nr == n;
}

void BS()
{
    double up = 1420, dw = 0, mid;
    while(up - dw > eps)
    {
        mid = (up + dw) / 2;
        if(OK(mid))
            up = mid;
        else
            dw = mid;
    }
    sol1 = up;
}

void Conect(int i, int j)
{
    g[s].push_back(i);
    g[j+n].push_back(d);
    g[i].push_back(j+n);
    g[j+n].push_back(i);
    c[s][i] = 1; c[j+n][d] = 1;
    cost[i][j+n] = cst[i][j];
    cost[j+n][i] = -cst[i][j];
    c[i][j+n] = 1;
}

void Build()
{
    s = 0; d = 2 * n + 1; nn = d + 2;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(cst[i][j] <= sol1)
                Conect(i, j);
}

bool Bellman_Ford()
{
    inq.assign(nn, 0);
    for(int i=0; i<nn; i++) dist[i] = oo;
    dist[s] = 0; q.push(s); inq[s] = 1;
    while(!q.empty())
    {
        int x = q.front(); inq[x] = 0; q.pop();
        for(unsigned i=0; i<g[x].size(); i++)
        if(c[x][newnn])
            if(dist[x] + cost[x][newnn] < dist[newnn])
            {
                t[newnn] = x;
                dist[newnn] = dist[x] + cost[x][newnn];
                if(!inq[newnn]) inq[newnn] = 1, q.push(newnn);
            }
    }
    return dist[d] != oo;
}

void Fmdcm()
{
    while(Bellman_Ford())
    {
        for(int j=d; j!=s; j=t[j])
            c[t[j]][j]--, c[j][t[j]]++;
        sol2 += dist[d];
    }
}

void Print()
{
    fout<<fixed;
    fout<<setprecision(5)<<sol1<<' '<<sol2;
}

int main()
{
    Read();
    BS();
    Build();
    Fmdcm();
    Print();
}