Cod sursa(job #1676401)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 aprilie 2016 21:41:00
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.89 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500;
const int NIL = -1;
const double EPS = 1e-6;
const int INF = 0x3F3F3F3F;

const int MAX_EDGES = 2 * MAX_N + 2 * MAX_N * MAX_N;

struct Point {
    double x, y;
};

struct Edge {
    int v;
    double cost;
    int cap;
    int next;
};

/* retea reziduala */
Edge G[MAX_EDGES];
int head[2 * MAX_N];
int ptr;

/* cuplaj */
bool used[MAX_N];
int L[MAX_N], R[MAX_N];

/* flux maxim de cost minim */
double D[2 * MAX_N];
int dad[2 * MAX_N];
int pointer[2 * MAX_N];
bool inQueue[2 * MAX_N];
int Q[1 << 18];

bool bellmanFord(int sink) {
    int b = 0, e = 1;
    Q[0] = 0;

    for (int i = 1; i <= sink; ++ i) {
        D[i] = static_cast <double> (INF);
    }

    while (b != e) {
        int u = Q[(b++) & 262143];
        inQueue[u] = 0;
        for (int i = head[u]; i != NIL; i = G[i].next) {
            int v = G[i].v;
            if (G[i].cap && D[v] > D[u] + G[i].cost) {
                D[v] = D[u] + G[i].cost;
                dad[v] = u;
                pointer[v] = i;
                if (!inQueue[v]) {
                    inQueue[v] = 1;
                    Q[(e++) & 262143] = v;
                }
            }
        }
    }
    return D[sink] != static_cast <double> (INF);
}

double FMCM(const int source, const int sink) {
    double cost = .0;
    while (bellmanFord(sink)) {
        cost += D[sink];
        int minFlow = INF;
        for (int i = sink; i != source; i = dad[i]) {
            minFlow = min(minFlow, G[pointer[i]].cap);
        }
        for (int i = sink; i != source; i = dad[i]) {
            G[pointer[i]].cap -= minFlow;
            G[pointer[i] ^ 1].cap += minFlow;
        }
    }
    return cost;
}

bool pairUp(int u) {
    if (used[u]) {
        return false;
    }
    used[u] = true;

    int i = head[u];
    while (i != NIL && R[G[i].v] != NIL) {
        i = G[i].next;
    }
    if (i == NIL) {
        i = head[u];
        while (i != NIL && !pairUp(R[G[i].v])) {
            i = G[i].next;
        }
    }
    if (i != NIL) {
        L[u] = G[i].v;
        R[G[i].v] = u;
        return true;
    } else {
        return false;
    }
}

bool matching(int n) {
    bool pushed;
    memset(L + 1, NIL, 4 * n);
    memset(R + 1, NIL, 4 * n);
    do {
        memset(used + 1, 0, n);
        pushed = false;
        for (int i = 1; i <= n; ++ i) {
            if (L[i] == NIL) {
                pushed |= pairUp(i);
            }
        }
    } while (pushed);

    int matched = 1;
    while (matched <= n && L[matched] != NIL) {
        ++ matched;
    }

    return matched == n + 1;
}

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

Point soldier[MAX_N];
Point shelter[MAX_N];
double dist[MAX_N][MAX_N];

void addEdge(int u, int v, int cap, double delta) {
    assert(ptr < MAX_EDGES);
    G[ptr].v = v;
    G[ptr].cap = cap;
    G[ptr].cost = delta;
    G[ptr].next = head[u];
    head[u] = ptr++;
}

int main() {
    ifstream fin("adapost.in");
    ofstream fout("adapost.out");
    fin.tie(0);
    ios_base::sync_with_stdio(false);

    int n; fin >> n;

    for (int i = 1; i <= n; ++ i) {
        fin >> soldier[i].x >> soldier[i].y;
    }

    for (int i = 1; i <= n; ++ i) {
        fin >> shelter[i].x >> shelter[i].y;
    }

    double b = static_cast <double> (1 << 12), e = .0;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            dist[i][j] = distance(soldier[i], shelter[j]);
            if (dist[i][j] > e) {
                e = dist[i][j];
            }
            if (dist[i][j] < b) {
                b = dist[i][j];
            }
        }
    }

    while (e - b > EPS) {
        double mid = (b + e) * .5;

        memset(head + 1, NIL, 4 * n);
        ptr = 0;

        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (mid - dist[i][j] >= EPS) {
                    addEdge(i, j, 0, 0);
                }
            }
        }

        if (matching(n)) {
            e = mid;
        } else {
            b = mid;
        }
    }

    fout << fixed << setprecision(5);
    fout << e << ' ';

    ptr = 0;
    memset(head, NIL, 8 * (n + 1));

    for (int i = 1; i <= n; ++ i) {
        addEdge(0, i, 1, 0);
        addEdge(i, 0, 0, 0);
    }

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (e - dist[i][j] >= EPS) {
                addEdge(i, n + j, 1, dist[i][j]);
                addEdge(n + j, i, 0, -1.0 * dist[i][j]);
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        addEdge(n + i, n + n + 1, 1, 0);
        addEdge(n + n + 1, n + i, 0, 0);
    }

    fout << FMCM(0, n + n + 1) << '\n';

    return 0;
}