Cod sursa(job #1223664)

Utilizator assa98Andrei Stanciu assa98 Data 28 august 2014 15:50:45
Problema Adapost Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.21 kb
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <fstream>
#include <cmath>
#include <cstring>

#define pe pair<double, double>
#define mp make_pair
#define fi first
#define se second

using namespace std;

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

const int MAX_N = 410;
const double INF = 200000000.0;

vector<pe> ad, sl;
int n;
double MAX_E;

vector<int> A[2 * MAX_N];
vector<int> B[MAX_N];

int S, D;
int c[2 * MAX_N][2 * MAX_N];
int f[2 * MAX_N][2 * MAX_N];
double cost[2 * MAX_N][2 * MAX_N];

double dist(pe a, pe b) {
    return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}

void graf() {
    S = 0;
    D = 2 * n + 1;
    for(int i = 1; i <= n; i++) {
        A[S].push_back(i);
        A[i].push_back(S);
        c[S][i] = 1;
    }
    for(int i = n + 1; i <= 2 * n; i++) {
        A[i].push_back(D);
        A[D].push_back(i);
        c[i][D] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = n + 1; j <= 2 * n; j++) {
            B[i].push_back(j - n);

            A[i].push_back(j);
            A[j].push_back(i);
            c[i][j] = 1;
            cost[i][j] = dist(sl[i - 1], ad[j - n - 1]);
            cost[j][i] = -cost[i][j];
        }
    }
}

int l[MAX_N];
int r[MAX_N];
bool viz[MAX_N];

bool pairup(int nod) {
    if(viz[nod]) {
        return false;
    }
    viz[nod] = true;

    for(auto it : B[nod]) {
        if(cost[nod][it + n] > MAX_E) {
            continue;
        }
        if(!r[it]) {
            l[nod] = it;
            r[it] = nod;
            return true;
        }
    }

    for(auto it : B[nod]) {
        if(cost[nod][it + n] > MAX_E) {
            continue;
        }
        if(pairup(r[it])) {
            l[nod] = it;
            r[it] = nod;
            return true;
        }
    }
    
    return false;
}

int cuplaj(double e) {
    MAX_E = e;
    
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));

    bool change = true;
    while(change) {
        change = false;
        memset(viz, 0, sizeof(viz));
        for(int i = 1; i <= n; i++) {
            if(!l[i] && pairup(i)) {
                change = true;
            }
        }
    }

    int sz = 0;
    for(int i = 1; i <= n; i++) {
        if(l[i]) {
            sz++;
        }
    }

    return sz;
}

double search(double st, double dr) {
    double ans = 0;
    for(int i = 1; i <= 60; i++) {
        double mij = (st + dr) / 2.0;
        if(cuplaj(mij) == n) {
            ans = mij;
            dr = mij;
        }
        else {
            st = mij;
        }
    }
    return ans;
}

bool inq[MAX_N * 2];
double d[MAX_N * 2];
int dad[MAX_N * 2]; 

double bellman() {
    for(int i = 1; i <= D; i++) {
        d[i] = INF;
        dad[i] = 0;
        inq[i] = 0;
    }
    
    queue<int> Q;
    Q.push(S);
    inq[S] = true;
    d[S] = 0;
    
    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        inq[nod] = false;
        if(nod == D) {
            continue;
        }
        for(auto it : A[nod]) {
            if(cost[nod][it] <= MAX_E && f[nod][it] < c[nod][it]) {
                if(d[nod] + cost[nod][it] < d[it]) {
                    d[it] = d[nod] + cost[nod][it];
                    dad[it] = nod;
                    if(!inq[it]) {
                        Q.push(it);
                        inq[it] = true;
                    }
                }
            }
        }
    }

    return d[D];
}   

double maxflow() {
    int fl = 0;
    double cost = 0;

    while(bellman() < INF) {
        int p = INF;
        for(int nod = D; nod != S; nod = dad[nod]) {
            p = min(p, c[dad[nod]][nod] - f[dad[nod]][nod]);
        }
        for(int nod = D; nod != S; nod = dad[nod]) {
            f[dad[nod]][nod] += p;
            f[nod][dad[nod]] -= p;
        }
        fl += p;
        cost += (double)d[D] * p;
    }

    return cost;
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        double a, b;
        fin >> a >> b;
        sl.push_back(mp(a, b));
    }
    for(int i = 1; i <= n; i++) {
        double a, b;
        fin >> a >> b;
        ad.push_back(mp(a, b));
    }

    graf();
    MAX_E = search(0.0, 5000.0);
    fout << fixed << setprecision(13);
    fout << MAX_E << ' ' << maxflow();
    
    return 0;
}