Cod sursa(job #1887956)

Utilizator antanaAntonia Boca antana Data 21 februarie 2017 20:52:36
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.1 kb
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>

#define x first
#define y second
#define MAXN 802
#define EPS (1e-12)
#define INF 0x3f3f3f3f

using namespace std;

vector <int> G[MAXN];
pair  <double, double> man[MAXN/2], house[MAXN/2];

double mincost, dist[MAXN], edges[MAXN*MAXN/4], cost[MAXN][MAXN];
int k, source, sink, n, q[MAXN*MAXN], dad[MAXN], left[MAXN], right[MAXN], flow[MAXN][MAXN], capacity[MAXN][MAXN];
bool seen[MAXN], inq[MAXN];

inline double mydistance(pair <double, double> p1, pair<double, double> p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

inline bool match(int node, double d)
{
    if(seen[node]) return 0;

    int i;

    seen[node] = 1;
    for(i=1; i<=n; ++i)
        if(!right[i+n] && cost[node][i+n] <= d) {
            left[node] = i+n;
            right[i+n] = node;
            return 1; }

    for(i=1; i<=n; ++i)
        if(cost[node][i+n] <= d && match(right[i+n], d)) {
            left[node] = n+i;
            right[n+i] = node;
            return 1; }

    return 0;
}

inline int computeMaxMatching(double d)
{
    int i, f = 1, ans = 0;

    memset(left, 0, sizeof left);
    memset(right, 0, sizeof right);

    while(f)
    {
        f = 0;
        memset(seen, 0, sizeof seen);
        for(i=1; i<=n; ++i)
            if(!left[i])
                f = f | match(i, d);
    }

    for(i=1; i<=n; ++i)
        if(left[i]) ans++;

    return ans;
}

inline bool bellmanford(double d)
{
    int node, son, i, left, right, lim;

    for(i=0; i<=2*n+1; ++i)
        dist[i] = 1.0*INF;
    dist[0] = 0;
    left = right = 0;
    q[right++] = source;
    inq[source] = 1;

    while(left < right) {
        node = q[left++];
        inq[node] = 0;
        if(node == sink) continue;

        lim = G[node].size();
        for(i=0; i<lim; ++i) {
            son = G[node][i];
            if(flow[node][son] < capacity[node][son] && dist[node] + cost[node][son] < dist[son]) {
                dist[son] = dist[node] + cost[node][son];
                dad[son] = node;
                if(!inq[son]) {
                    inq[son] = 1;
                    q[right++] = son; } } } }


    return (dist[sink] != INF);
}

inline int pump(double d)
{
    int node, minflow = INF;

    for(node=sink; node!=source; node=dad[node])
        minflow = min(minflow, capacity[dad[node]][node] - flow[dad[node]][node]);
    if(minflow)
        for(node=sink; node!=source; node=dad[node])
            flow[dad[node]][node] += minflow, flow[node][dad[node]] -= minflow;

    mincost += minflow*dist[sink];

    return minflow;
}

inline int computeMaxFlow(double d)
{
    double maxflow = 0;
    mincost = 0;

    while(bellmanford(d)) maxflow += pump(d);

    return maxflow;
}

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

    int i, j, ans, step = 1;
    double f;

    scanf("%d", &n);

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

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

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j) {
            cost[i][j+n] = mydistance(man[i], house[j]);
            cost[j+n][i] = -cost[i][j+n];
            edges[++k] = cost[i][j+n]; }

    source = 0;
    sink = 2*n+1;

    sort(edges+1, edges+k+1);

    while((step << 1) <= k) step<<=1;

    ans = 0;
    for(; step>=1; step>>=1)
        if(ans+step <= k && computeMaxMatching(edges[ans+step]) < n)
            ans += step;

    for(i=1; i<=n; ++i)
    {
        G[0].push_back(i);
        G[i].push_back(0);
        capacity[0][i] = 1;

        G[i+n].push_back(2*n+1);
        G[2*n+1].push_back(i+n);
        capacity[i+n][2*n+1] = 1;

        for(j=n+1; j<=2*n; ++j)
            if(cost[i][j] <= edges[ans+1])
                G[i].push_back(j), G[j].push_back(i), capacity[i][j] = 1;
    }

    f = computeMaxFlow(edges[ans+1]);

    printf("%.5lf %.5lf", edges[ans+1], mincost);

    return 0;
}