Cod sursa(job #917989)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 15:35:05
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.92 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define MAX_N 810
#define inf 1000000000
 
#define eps 0.000001
 
#define mp make_pair
 
int n, m, s, d, k;
 
int viz[MAX_N], cuplaj[MAX_N];
 
double dmin = inf, sol;
 
vector <int> G[MAX_N];
 
bool improve;
 
int C[MAX_N][MAX_N], F[MAX_N][MAX_N];
double cost[MAX_N][MAX_N];
 
int tata[MAX_N], h[MAX_N], pos[MAX_N];
double D[MAX_N];
 
struct punct {
    double x, y;
} A[MAX_N], B[MAX_N];
 
inline double dist(int p, int q) {
    return sqrt((A[p].x - B[q].x) * (A[p].x - B[q].x) + (A[p].y - B[q].y) * (A[p].y - B[q].y));
}
 
void get_graph(double k) {
    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 (dist(i, j) <= k + eps)
                G[i].push_back(j);
}
 
bool cupleaza(int x) {
    if (viz[x])
        return false;
    viz[x] = 1;
 
    for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
        if (cuplaj[*it] == 0) {
            cuplaj[*it] = x;
            m++;
            return true;
        }
 
    for (vector <int>::iterator it = G[x].begin(); it != G[x].end(); ++it)
        if (cuplaj[*it] != x && cupleaza(cuplaj[*it])) {
            cuplaj[*it] = x;
            return true;
        }
 
    return false;
}
 
void get_dmin() {
    double value[MAX_N * MAX_N];
     
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            value[(i - 1) * n + j] = dist(i, j);
    sort(value + 1, value + n * n + 1);
 
    int left = 0, right = n * n + 1, mid = 0;
    while (left + 1 < right) {
        mid = (left + right) / 2;
 
        get_graph(value[mid]);
 
        memset(cuplaj, 0, sizeof(cuplaj)); m = 0;
 
        for (int i = 1; i <= n; i++) {
            memset(viz, 0, sizeof(viz));
            cupleaza(i);
        }
 
        if (m == n) {
            right = mid;
            dmin = min(dmin, value[mid]);
        }
        else
            left = mid;
    }
}
 
void build_flow_graph() {
    s = 1; d = 2 * n + 2;
 
    for (int i = 1; i <= d; i++)
        vector <int> ().swap(G[i]);
 
    for (int i = 1; i <= n; i++) {
        G[s].push_back(i + 1); C[s][i + 1] = 1;
        G[i + 1].push_back(s);
 
        G[n + i + 1].push_back(d); C[n + i + 1][d] = 1;
        G[d].push_back(n + i + 1);
    }
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist(i, j) <= dmin + eps) {
                G[i + 1].push_back(n + j + 1); cost[i + 1][n + j + 1] = dist(i, j); C[i + 1][n + j + 1] = 1;
                G[n + j + 1].push_back(i + 1); cost[n + j + 1][i + 1] = -cost[i + 1][n + j + 1];
            }
}
 
void heap_update(int x) {
    //down-heap
    while (x > 1 && D[h[x / 2]] > D[h[x]]) {
        swap(h[x], h[x / 2]);
        pos[h[x]] = x; pos[h[x / 2]] = x / 2;
 
        x /= 2;
    }
 
    //up-heap
    while ((x * 2 <= k && D[h[x * 2]] < D[h[x]]) || (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x]])) {
        int nxt = x * 2;
        if (x * 2 + 1 <= k && D[h[x * 2 + 1]] < D[h[x * 2]])
            nxt = x * 2 + 1;
 
        swap(h[x], h[nxt]);
        pos[h[x]] = x; pos[h[nxt]] = nxt;
 
        x = nxt;
    }
}
 
double dijkstra() {
    for (int i = 1; i <= d; i++) {
        D[i] = inf;
        tata[i] = viz[i] = 0;
    }
    D[s] = 0;
 
    h[k = 1] = s; pos[s] = viz[s] = 1;
    while (k) {
        int nod = h[1];
 
        swap(h[1], h[k]);
        pos[h[1]] = 1; pos[h[k]] = 0; k--;
        heap_update(1);
         
        viz[nod] = 0;
 
        for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
            if (C[nod][*it] > F[nod][*it] && D[*it] > D[nod] + cost[nod][*it]) {
                D[*it] = D[nod] + cost[nod][*it];
 
                if (viz[*it] == 0) {
                    h[++k] = *it;
                    pos[*it] = k;
                }
 
                heap_update(pos[*it]);
                viz[*it] = 1;
                tata[*it] = nod;
            }
        }
    }
 
    if (D[d] != inf) {
        improve = true;
 
        for (int i = d; i != s; i = tata[i]) {
            F[tata[i]][i]++;
            F[i][tata[i]]--;
        }
     
        return D[d];
    }
     
    return 0;
}
 
void solve() {
    get_dmin(); 
 
    build_flow_graph();
 
    improve = true;
    while (improve) {
        improve = false;
         
        sol += dijkstra();
    }
     
    printf("%lf %lf\n", dmin, sol);
}
 
int main() {
 
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf", &A[i].x, &A[i].y);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf", &B[i].x, &B[i].y);
 
    solve();
 
    return 0;
}