Cod sursa(job #1887820)

Utilizator antanaAntonia Boca antana Data 21 februarie 2017 19:36:27
Problema Adapost Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.33 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], BP[MAXN];
pair  <double, double> man[MAXN/2], house[MAXN/2];

double mincost, cost[MAXN][MAXN], dist[MAXN], edges[MAXN*MAXN/4];
char flow[MAXN][MAXN], capacity[MAXN][MAXN];
int k, source, sink, n;
short int q[MAXN*MAXN], dad[MAXN], left[MAXN], right[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=0; i<G[node].size(); ++i)
        if(!right[G[node][i]] && cost[node][G[node][i]] <= d) {
            left[node] = G[node][i];
            right[G[node][i]] = node;
            return 1; }

    for(i=0; i<G[node].size(); ++i)
        if(cost[node][G[node][i]] <= d && match(right[G[node][i]], d)) {
            left[node] = G[node][i];
            right[G[node][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;

    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;

        for(i=0; i<G[node].size(); ++i) {
            son = G[node][i];
            if(cost[node][son] < d+EPS && 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;
    int 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)
{
    int i, j;
    double maxflow = 0;
    mincost = 0;

    for(i=0; i<=2*n+1; ++i)
        for(j=0; j<=2*n+1; ++j)
            flow[i][j] = 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];
            capacity[i][j+n] = 1;
            G[i].push_back(j+n);
            BP[i].push_back(j+n);
            G[j+n].push_back(i); }

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

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

    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;

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

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

    return 0;
}