Cod sursa(job #2242646)

Utilizator LucaSeriSeritan Luca LucaSeri Data 19 septembrie 2018 09:41:10
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 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-3;

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];
bool viz[MAXN];
int tata[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;
    }
};

bool dijkstra (double lim) {
    priority_queue< pair< int, double >, vector< pair< int, double > >, cmp > H;
    H.push(make_pair(source, 0));
    for(int i = 1; i <= target; ++i) dist[i] = 1e9;
    memset(viz, 0, sizeof viz);
    memset(tata, 0, sizeof tata);
    while(H.size()) {
        int node;
        double curcost;
        tie(node, curcost) = H.top();
        H.pop();
        if(viz[node]) continue;
        viz[node] = true;

        for(int i = 0; i <= target; ++i) {
            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]));
               }
        }
    }

    for(int i = 1; i <= target; ++i) potential[i] = dist[i];
    return (tata[target] != 0);
}

double flowCost = 0;
double totalFlow = 0;

bool perfectMatching(double lim) {
    memset(currentFlow, 0, sizeof currentFlow);
    memset(potential, 0, sizeof potential);
    flowCost = 0;
    totalFlow = 0;
    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 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) {
            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) {
        capacity[source][i] = 1;
        capacity[i + n][target] = 1;
    }

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

    g.precision(10);
    g << fixed;
    g << ans1 << ' ' << ans2;
    return 0;
}