Cod sursa(job #2242869)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 septembrie 2018 17:35:47
Problema Adapost Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.45 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("adapost.in");
ofstream g("adapost.out");
int n;
const int MAXN = 810;

const int source = 0;
const int target = 801;
const double eps = 1e-5;

int currentFlow[MAXN][MAXN];
int capacity[MAXN][MAXN];

pair< double, double > sold[MAXN];
pair< double, double > ad[MAXN];

double cost[MAXN][MAXN];
double dist[MAXN];
double potential[MAXN];
int tata[MAXN];
vector< int > gr[MAXN];

double d(pair< double, double > a, pair< double, double > b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

class cmp {
public:
    const bool operator() (const pair< int , double > &a, const pair< int, double > &b) const {
        return a.second > b.second;
    }
};

priority_queue< pair< int, double >, vector< pair< int, double > >, cmp > H;
bool dijkstra (double lim) {
    H.push(make_pair(source, 0));
    for(int i = 1; i <= target; ++i) dist[i] = 1e9;
    tata[target] = 0;
    while(H.size()) {
        int node;
        double curcost;
        tie(node, curcost) = H.top();
        H.pop();
        if(curcost != dist[node]) continue;
        for(auto &i : gr[node]) {
            if(currentFlow[node][i] < capacity[node][i] && cost[node][i] < lim + eps &&
               curcost + cost[node][i] + potential[node] - potential[i] < dist[i]) {
                    dist[i] = curcost + cost[node][i] + potential[node] - potential[i];
                    tata[i] = node;
                    H.push(make_pair(i, dist[i]));
               }
        }
    }

    memcpy(potential, dist, sizeof potential);
    return (tata[target] != 0);
}

double flowCost = 0;
double totalFlow = 0;

bool perfectMatching(double lim) {
    while(dijkstra(lim)) {
        int node = target;
        int minim = 1e9;
        while(node) {
            minim = min(minim, capacity[tata[node]][node] - currentFlow[tata[node]][node]);
            node = tata[node];
        }

        node = target;
        while(node) {
            currentFlow[tata[node]][node] += minim;
            currentFlow[node][tata[node]] -= minim;
            node = tata[node];
        }

        totalFlow +=  minim;
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(currentFlow[i][n + j]) flowCost += cost[i][n + j];
        }
    }
    return (totalFlow == n);
}

int lft[MAXN], rght[MAXN];
bool vizz[MAXN];
int cnt = 0;
bool cuplaj(int node, double lim) {
    if(vizz[node]) return false;
    vizz[node] = true;

    for(auto &x : gr[node]) {
        if(!lft[x] && cost[node][x] < lim + eps) {
            lft[x] = node;
            rght[node] = x;
            ++cnt;
            return true;
        }
    }

    for(auto &x : gr[node]) {
        if(cost[node][x] < lim + eps && cuplaj(lft[x], lim)) {
            lft[x] = node;
            rght[node] = x;
            return true;
        }
    }

    return false;
}
bool ok(double lim) {
    memset(lft, 0, sizeof lft);
    memset(rght, 0, sizeof rght);
    lft[0] = -1;
    cnt = 0;
    bool k = true;
    while(k) {
        k = false;
        memset(vizz, 0, sizeof vizz);
        for(int i = 1; i <= n; ++i) {
            if(!rght[i]) k |= cuplaj(i, lim);
        }
    }

    return (cnt == n);
}
int main(){
    f >> n;
    for(int i = 1; i <= n; ++i) {
        f >> sold[i].first >> sold[i].second;
    }

    for(int i = 1; i <= n; ++i) {
        f >> ad[i].first >> ad[i].second;
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            gr[i].emplace_back(n + j);
            gr[n + j].emplace_back(i);
            cost[i][n + j] = d(sold[i], ad[j]);
            cost[n + j][i] = -d(sold[i], ad[j]);
            capacity[i][n + j] = 1;
        }
    }

    for(int i = 1; i <= n; ++i) {
        gr[source].emplace_back(i);
        gr[i].emplace_back(source);
        gr[i + n].emplace_back(target);
        gr[target].emplace_back(i + n);
        capacity[source][i] = 1;
        capacity[i + n][target] = 1;
    }

    double ans = -1;
    double lo = 0, hi = 1500;
    while(abs(lo - hi) > eps) {
        double mid = (lo + hi) / 2;
        if(ok(mid)) {
            ans = mid;
            hi = mid;
        } else {
            lo = mid;
        }
    }

    perfectMatching(ans);
    g.precision(10);
    g << fixed;
    g << ans << ' ' << flowCost;
    return 0;
}