Cod sursa(job #989897)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 26 august 2013 20:20:44
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

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

const double oo = 2e9, er = 1e-4;
const int N = 810, d = 805;

#define xx first
#define yy second

typedef pair <double, double> coord;

int C[N][N], n, t[N], cuplaj, A[N], B[N];
double cost[N][N], cst, dmin = oo, v[N*N/4], c[N];
coord memleft[N], memright[N];
queue <int> Q;
bool q[N], viz[N];
vector <int> g[N];

bool match(int x) {
    if (viz[x])
        return 0;
    viz[x] = 1;
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (!B[*it]) {
            B[*it] = x;
            A[x] = *it;
            cuplaj++;
            return 1;
        }
    for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (B[*it] != x && match(B[*it])) {
            B[*it] = x;
            A[x] = *it;
            return 1;
        }
    return 0;
}

bool go(double x) {
    for (int i = 1; i <= n; ++i)
        vector <int> ().swap(g[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (cost[i][n+j] <= x + er)
                g[i].push_back(j);
        }
    for (int i = 1; i <= n; ++i)
        viz[i] = 0, A[i] = B[i] = 0;
    cuplaj = 0;
    bool ok = 1;
    while (ok) {
        ok = 0;
        for (int i = 1; i <= n; ++i)
            viz[i] = 0;
        for (int i = 1; i <= n; ++i)
            if (!A[i])
                ok |= match(i);
    }
    return (cuplaj == n);
}

bool bellmanford() {
    Q.push(0);
    for (int i = 1; i <= n * 2; ++i)
        c[i] = oo;
    c[d] = oo;
    while (Q.size()) {
        int x = Q.front(); Q.pop();
        q[x] = 0;
        for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
            if (C[x][*it]) {
                double NEW = c[x] + cost[x][*it];
                if (NEW < c[*it] + er) {
                    c[*it] = NEW;
                    t[*it] = x;
                    if (!q[*it]) {
                        q[*it] = 1;
                        Q.push(*it);
                    }
                }
            }
        }
    }
    return (c[d] != oo);
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> memleft[i].xx >> memleft[i].yy;
    for (int i = 1; i <= n; ++i)
        fin >> memright[i].xx >> memright[i].yy;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            double now = sqrt ((memleft[i].xx - memright[j].xx) * (memleft[i].xx - memright[j].xx) + (memleft[i].yy - memright[j].yy) * (memleft[i].yy - memright[j].yy));
            cost[i][n+j] = now;
            cost[n+j][i] = -now;
            v[(i - 1) * n + j - 1] = now;
        }
    sort (v, v + n * n);
    int lo = 0, hi = n * n;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (go(v[mid])) {
            dmin = min (dmin, v[mid]);
            hi = mid;
        }
        else
            lo = mid + 1;
    }
    for (int i = 1; i <= n; ++i)
        vector <int> ().swap(g[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (cost[i][n+j] <= dmin + er) {
                g[i].push_back(n + j); g[n + j].push_back(i);
                C[i][n + j] = 1;
            }
        }
    for (int i = 1; i <= n; ++i) {
        g[0].push_back(i);
        C[0][i] = 1;
        g[n+i].push_back(d);
        C[n+i][d] = 1;
    }
    while (bellmanford()) {
        cst += c[d];
        for (int x = d; x; x = t[x])
            C[t[x]][x]--, C[x][t[x]]++;
    }
    fout << fixed << setprecision(5) << dmin << " " << cst;
    fout.close();
}