Cod sursa(job #1414058)

Utilizator SmarandaMaria Pandele Smaranda Data 2 aprilie 2015 12:16:15
Problema Adapost Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.75 kb
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdio>

using namespace std;

const int N = 404, inf = (1ll << 31) - 1;

struct Point {
    double x, y;
};

int d [N][2 * N], a [2 * N], b [2 * N], l [2 * N], c [2 * N + 2][2 * N + 2], father [2 * N + 2], f [2 * N + 2][2 * N + 2];
bool used [2 * N];
vector <int> graph [N];
Point S [N], D [N];
int n;

double dist (const Point &A, const Point &B) {
    return sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

bool cupleaza (int x) {
    vector <int> :: iterator it;

    if (used [x] == 1)
        return 0;
    used [x] = 1;
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (!b [*it]) {
            b [*it] = x;
            a [x] = *it;
            return 1;
        }
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (b [*it]) {
            if (cupleaza (b [*it]) && b [*it] != x) {
                a [x] = *it;
                b [*it] = x;
                return 1;
            }
        }
    return 0;
}

int cuplaj () {
    int i, flag = 1, ans = 0;

    memset (a, 0, sizeof (a));
    memset (b, 0, sizeof (b));
    memset (used, 0, sizeof (used));

    while (flag) {
        flag = 0;
        memset (used, 0, sizeof (used));
        for (i = 1; i <= n; i ++)
            if (!a [i])
                if (cupleaza (i)) {
                    flag = 1;
                    ++ ans;
                }
    }
    return ans;
}

void make_graph (int dmax, int capacitati) {
    int i, j, lim = 2 * n;

    for (i = 1; i <= n; i ++) {
        graph [i].clear ();
        for (j = n + 1; j <= lim; j ++)
            if (d [i][j] <= dmax) {
                graph [i].push_back (j);
                if (capacitati == 1) {
                    graph [j].push_back (i);
                    c [i][j] = 1;
                }
            }
    }
}

bool ok (int dmax) {
    make_graph (dmax, 0);
    if (cuplaj () == n)
        return 1;
    return 0;
}

bool bellmanford (int sursa, int destinatie) {
    int i, x;
    vector <int> :: iterator it;
    queue <int> q;

    for (i = 0; i <= destinatie; i ++)
        l [i] = inf;
    memset (used, 0, sizeof (used));
    q.push (sursa);
    l [sursa] = 0;
    used [sursa] = 1;
    while (!q.empty ()) {
        x = q.front ();
        q.pop ();
        used [x] = 0;
        for (it = graph [x].begin (); it != graph [x].end (); ++ it)
            if (c [x][*it] - f [x][*it] > 0 && l [*it] > l [x] + d [x][*it]) {
                l [*it] = l [x] + d [x][*it];
                father [*it] = x;
                if (used [*it] == 0) {
                    q.push (*it);
                    used [*it] = 1;
                }
            }
    }
    if (l [destinatie] != inf)
        return 1;
    return 0;
}

int fmcm (int sursa, int destinatie) {
    int minflow, i, ans = 0;

    while (bellmanford (sursa, destinatie)) {
        minflow = inf;
        for (i = destinatie; i != sursa; i = father [i])
            minflow = min (minflow, c [father [i]][i] - f [father [i]][i]);
        if (minflow == 0)
            continue;
        for (i = destinatie; i != sursa; i = father [i]) {
            f [father [i]][i] += minflow;
            f [i][father [i]] -= minflow;
        }
         ans = ans + minflow * l [destinatie];
    }
    return ans;
}

int main () {
    int i, j, dmax, last, sursa, destinatie, ans, st, dr, m;
    double k;

    freopen ("adapost.in", "r", stdin);
    freopen ("adapost.out", "w", stdout);

    scanf ("%d", &n);
    for (i = 1; i <= n; i ++)
        scanf ("%lf%lf", &S [i].x, &S [i].y);
    for (i = 1; i <= n; i ++)
        scanf ("%lf%lf", &D [i].x, &D [i].y);

    for (i = 1; i <= n; i ++)
        for (j = 1; j <= n; j ++) {
            k = dist (S [i], D [j]);
            d [i][j + n] = k * 10000;
            d [j + n][i] = - d [i][j + n];
            if (d [i][j + n] > dmax)
                dmax = d [i][j + n];
        }

    st = 0;
    dr = dmax;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (ok (m)) {
            dr = m - 1;
            last = m;
        }
        else st = m + 1;
    }
    k = 1.0 * last / 10000;
    printf ("%lf", k);
    make_graph (last, 1);
    sursa = 0;
    destinatie = 2 * n + 1;
    for (i = 1; i <= n; i ++) {
        graph [sursa].push_back (i);
        graph [i].push_back (sursa);
        c [sursa][i] = 1;
    }
    for (i = 1; i <= n; i ++) {
        graph [i + n].push_back (destinatie);
        graph [destinatie].push_back (i + n);
        c [i + n][destinatie] = 1;
    }
    ans = fmcm (sursa, destinatie);
    k = 1.0 * ans / 10000;
    printf (" %lf\n", k);
    return 0;
}