Cod sursa(job #1662327)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 24 martie 2016 17:50:28
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
#include <queue>

using namespace std;

const int NMAX = 405;

int n;
struct point {
    double x, y;
    point(double _x = 0, double _y = 0): x(_x), y(_y) {}
} soldati[NMAX], adaposturi[NMAX];

double dist(const point &a, const point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

pair <double, pair <int, int> > all_dists[NMAX * NMAX];

vector <int> matching_graph[NMAX];

int _left[NMAX];
int _right[NMAX];
bitset <2 * NMAX> vis;

void build_matching_graph(int edges_count) {
    for (int i = 1; i <= edges_count; ++ i)
        matching_graph[all_dists[i].second.first].push_back(all_dists[i].second.second);
}

void destruct_matching_graph(int edges_count) {
    for (int i = 1; i <= edges_count; ++ i)
        matching_graph[all_dists[i].second.first].clear();
}

bool pair_up(int node) {
    if (vis[node])
        return false;
    vis[node] = true;

    for (auto it: matching_graph[node])
        if (!_right[it]) {
            _left[node] = it;
            _right[it] = node;
            return true;
        }

    for (auto it: matching_graph[node])
        if (pair_up(_right[it])) {
            _left[node] = it;
            _right[it] = node;
            return true;
        }

    return false;
}

int maximum_matching() {
    memset(_left, 0, sizeof _left);
    memset(_right, 0, sizeof _right);

    bool done = false;
    while (!done) {
        done = true;

        vis &= 0;
        for (int i = 1; i <= n; ++ i)
            if (!_left[i] && pair_up(i))
                done = false;
    }

    int matching_count = 0;
    for (int i = 1; i <= n; ++ i)
        matching_count += (bool)_left[i];
    return matching_count;
}

//Mincost Maxflow
int N, s, t;
vector <int> graph[2 * NMAX];

int cap[2 * NMAX][2 * NMAX];
double cost[2 * NMAX][2 * NMAX];

void add_edge(int a, int b, double c) {
    graph[a].push_back(b);
    graph[b].push_back(a);

    cap[a][b] = 1;
    cost[a][b] += c;
    cost[b][a] -= c;
}

queue <int> _queue;
bool in_queue[2 * NMAX];

double potentials[2 * NMAX];

const double INF = 1e14;

void bellman(){
    for (int i = 1; i <= N; ++ i) {
        in_queue[i] = false;
        potentials[i] = INF;
    }

    in_queue[s] = true;
    potentials[s] = 0;
    _queue.push(s);


    int node;
    while (!_queue.empty()) {
        node = _queue.front();
        _queue.pop();
        in_queue[node] = false;

        for (auto it: graph[node])
            if (cap[node][it] && potentials[node] + cost[node][it] < potentials[it]) {
                potentials[it] = potentials[node] + cost[node][it];
                if (!in_queue[it]) {
                    _queue.push(it);
                    in_queue[it] = true;
                }
            }
    }
}

priority_queue <pair <double, int>, vector <pair <double, int> >, greater <pair <double, int> > > _priority_queue;

double d[2 * NMAX];
int father[2 * NMAX];

bool dijkstra() {
    for (int i = 1; i <= N; ++ i)
        d[i] = INF;
    _priority_queue.push(make_pair(0, s));
    d[s] = 0;

    vis &= 0;

    int node;
    while (!_priority_queue.empty()) {
        node = _priority_queue.top().second;
        _priority_queue.pop();

        if (vis[node])
            continue;
        vis[node] = true;
        for (auto it: graph[node])
            if (cap[node][it] && d[node] + cost[node][it] + potentials[node] - potentials[it] < d[it]) {
                d[it] = d[node] + cost[node][it] + potentials[node] - potentials[it];
                father[it] = node;
                _priority_queue.push(make_pair(d[it], it));
            }
    }

    return vis[t];
}

double mincost_flow() {
    bellman();

    double ans = 0;
    while (dijkstra()) {
        int node = t;
        while (father[node]) {
            cap[father[node]][node] -= 1;
            cap[node][father[node]] += 1;

            ans += cost[father[node]][node];

            node = father[node];
        }

        for (int i = 1; i <= N; ++ i)
            d[i] -= (potentials[s] - potentials[i]);
        memcpy(potentials, d, sizeof(double) * (N + 2));
    }

    return ans;
}

int main()
{
    ifstream cin("adapost.in");
    ofstream cout("adapost.out");

    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> soldati[i].x >> soldati[i].y;
    for (int i = 1; i <= n; ++ i)
        cin >> adaposturi[i].x >> adaposturi[i].y;

    int pos = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            all_dists[++ pos] = make_pair(dist(soldati[i], adaposturi[j]), make_pair(i, j));
    sort(all_dists + 1, all_dists + pos + 1);

    int st = 1;
    int dr = pos - 1;
    int mid;
    int ans = pos;

    while (st <= dr) {
        mid = (st + dr) >> 1;

        build_matching_graph(mid);
        if (maximum_matching() == n) {
            ans = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
        destruct_matching_graph(mid);
    }

    cout << fixed << setprecision(5) << all_dists[ans].first << ' ';

    //Construim graful de flux
    for (int i = 1; i <= ans; ++ i)
        add_edge(all_dists[i].second.first, n + all_dists[i].second.second, all_dists[i].first);

    s = 2 * n + 1;
    t = 2 * n + 2;
    N = t;

    for (int i = 1; i <= n; ++ i) {
        add_edge(s, i, 0);
        add_edge(n + i, t, 0);
    }

    cout << mincost_flow() << '\n';

    cin.close();
    cout.close();
    return 0;
}