Cod sursa(job #2073002)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 22 noiembrie 2017 16:48:26
Problema Adapost Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.13 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 805;

struct Muchie {
    int to, rev, flow, cap, cost;
};

struct Nod {
    int nod, cost;
    bool operator > (Nod other) const {
        return cost > other.cost;
    }
};

vector <Muchie> g[nmax];
double x[nmax], y[nmax];
int n, src, dest, med;
int dist[nmax], distdij[nmax];
bool viz[nmax];
int prevnode[nmax], prevedge[nmax], prevflow[nmax];

int distPct(int i, int j) {
    double dis = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    return dis * 1000;
}

void bellmanford() {
    for(int from = 0; from <= dest; ++ from) {
        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie& e = g[from][k];
            e.flow = 0;
        }
    }

    fill(dist, dist + dest + 1, INT_MAX);
    queue <int> q;
    dist[src] = 0;
    q.push(src);

    while(!q.empty()) {
        int from = q.front();

        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie& e = g[from][k];
            int aux = dist[from] + e.cost;

            if(e.flow < e.cap && aux < dist[e.to] && abs(e.cost) <= med) {
                dist[e.to] = aux;
                q.push(e.to);
            }
        }

        q.pop();
    }
}

void dijkstra() {
    fill(distdij, distdij + dest + 1, INT_MAX);
    fill(viz, viz + dest + 1, 0);
    priority_queue <Nod, vector<Nod>, greater<Nod>> q;
    distdij[src] = 0;
    prevflow[src] = INT_MAX;
    q.push({src, 0});

    while(!q.empty()) {
        int from = q.top().nod;

        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie& e = g[from][k];
            int aux = distdij[from] + dist[from] - dist[e.to] + e.cost;

            if(e.flow < e.cap && aux < distdij[e.to] && abs(e.cost) <= med) {
                distdij[e.to] = aux;
                q.push({e.to, aux});

                prevnode[e.to] = from;
                prevedge[e.to] = k;
                prevflow[e.to] = min(prevflow[from], e.cap - e.flow);
            }
        }

        q.pop();
    }
}

int mincutflow(int& p) {
    int maxCostSingle = 0, cost = 0, flow = 0;

    bellmanford();
    dijkstra();

    while(distdij[dest] < INT_MAX) {
        int deltaFlow = prevflow[dest];
        flow += deltaFlow;

        for(int i = dest; i != src; i = prevnode[i]) {
            Muchie& e = g[prevnode[i]][prevedge[i]];

            e.flow += deltaFlow;
            g[e.to][e.rev].flow -= deltaFlow;
            cost += e.cost * deltaFlow;
        }

        for(int i = 0; i <= dest; ++ i) {
            dist[i] += distdij[i];
        }

        dijkstra();
    }

    for(int from = 1; from <= n; ++ from) {
        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie& e = g[from][k];

            if(e.to != dest && e.flow == e.cap) {
                maxCostSingle = max(maxCostSingle, e.cost);
            }
        }
    }

    p = cost;
    return flow;
}

void binar() {
    int st = 0, dr = 2000000, last = -1, lastCost, aux;
    while(st <= dr) {
        med = (st + dr) / 2;
        if(mincutflow(aux) == n) {
            dr = med - 1;
            last = med;
            lastCost = aux;
        } else {
            st = med + 1;
        }
    }
    printf("%d.%03d %d.%03d", last / 1000, last % 1000, lastCost / 1000, lastCost % 1000);
}

int main() {
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);

    scanf("%d", &n);
    dest = n + n + 1;

    for(int i = 1; i <= n + n; ++ i) {
        scanf("%lf%lf", &x[i], &y[i]);
    }

    for(int i = 1; i <= n; ++ i) {
        for(int j = n + 1; j <= n + n; ++ j) {
            g[i].push_back({j, g[j].size(), 0, 1, distPct(i, j)});
            g[j].push_back({i, g[i].size() - 1, 0, 0, -distPct(i, j)});
        }
    }

    for(int i = 1; i <= n; ++ i) {
        g[src].push_back({i, g[i].size(), 0, 1, 0});
        g[i].push_back({src, g[src].size() - 1, 0, 0, 0});

        g[i + n].push_back({dest, g[dest].size(), 0, 1, 0});
        g[dest].push_back({i + n, g[i + n].size() - 1, 0, 0, 0});
    }

    binar();

    return 0;
}