Cod sursa(job #830780)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 decembrie 2012 18:04:00
Problema Adapost Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.33 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <queue>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const int MaxN = 805;
const double oo = 1000000.0;
const double Eps = 1e-5;

Point Points[MaxN];
vector<int> G[MaxN];
int N, Source, Sink, Capacity[MaxN][MaxN], Flow[MaxN][MaxN], Father[MaxN];
double Cost[MaxN][MaxN], Distance[MaxN], FlowMinCost;
double SolutionMax, SolutionCost;
bool InQ[MaxN], Used[MaxN];
queue<int> Q;
int L[MaxN], R[MaxN];

inline double PointDistance(const Point P1, const Point P2) {
    return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}

inline void AddEdge(const int x, const int y, const int capacity, const double cost) {
    G[x].push_back(y), G[y].push_back(x);
    Capacity[x][y] = capacity, Capacity[y][x] = 0;
    Cost[x][y] = cost, Cost[y][x] = -cost;
}

void BuildGraph() {
    Source = 0, Sink = 2 * N + 1;
    for (int X = 1; X <= N; ++X) {
        AddEdge(Source, X, 1, 0);
        for (int Y = N + 1; Y <= 2 * N; ++Y)
            AddEdge(X, Y, 1, PointDistance(Points[X], Points[Y]));
    }
    for (int X = N + 1; X <= 2 * N; ++X)
        AddEdge(X, Sink, 1, 0);
}

inline void InitBellmanFord(const int Start) {
    for (int X = 0; X <= 2 * N + 1; ++X)
        InQ[X] = false, Distance[X] = oo, Father[X] = -1;
    Distance[Start] = 0;
    Q.push(Start), InQ[Start] = true;
}

bool BellmanFord(const int Start, const int End) {
    for (InitBellmanFord(Start); !Q.empty(); Q.pop()) {
        int X = Q.front(); InQ[X] = false;
        for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
            if (Capacity[X][*Y] > Flow[X][*Y] && Distance[X] + Cost[X][*Y] < Distance[*Y]) {
                Distance[*Y] = Distance[X] + Cost[X][*Y], Father[*Y] = X;
                if (!InQ[*Y])
                    Q.push(*Y), InQ[*Y] = true;
            }
        }
    }
    return Father[End] != -1;
}

double MaximumFlow() {
    int MaxFlow = 0; double MinCost = 0;
    while (BellmanFord(Source, Sink)) {
        int CurrentFlow = N;
        for (int X = Sink; X != Source; X = Father[X])
            CurrentFlow = min(CurrentFlow, Capacity[Father[X]][X] - Flow[Father[X]][X]);
        for (int X = Sink; X != Source; X = Father[X])
            Flow[Father[X]][X] += CurrentFlow, Flow[X][Father[X]] -= CurrentFlow;
        MaxFlow += CurrentFlow, MinCost += CurrentFlow * Distance[Sink];
    }
    return MinCost;
}

int PairUp(const int X, const double MaxCost) {
    if (Used[X])
        return 0;
    Used[X] = true;
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (*Y != Source && abs(Cost[X][*Y]) <= MaxCost && !L[*Y]) {
            R[X] = *Y, L[*Y] = X;
            return 1;
        }
    }
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (*Y != Source && abs(Cost[X][*Y]) <= MaxCost && PairUp(L[*Y], MaxCost)) {
            R[X] = *Y, L[*Y] = X;
            return 1;
        }
    }
    return 0;
}

int MaximumMatching(const double MaxCost) {
    memset(L, 0, sizeof(L)), memset(R, 0, sizeof(R));
    for (int Change = 1; Change != 0; ) {
        Change = 0, memset(Used, 0, sizeof(Used));
        for (int X = 1; X <= N; ++X)
            if (!R[X] && !Used[X])
                Change |= PairUp(X, MaxCost);
    }
    int MaxMatching = 0;
    for (int X = 1; X <= N; ++X)
        MaxMatching += (R[X] != 0);
    return MaxMatching;
}

void Solve() {
    BuildGraph();
    double Left = 0, Right = oo;
    while (Right - Left > Eps) {
        double Middle = 0.5 * (Left + Right);
        if (MaximumMatching(Middle) == N)
            Right = Middle - Eps, SolutionMax = Middle;
        else
            Left = Middle + Eps;
    }
    for (int X = 0; X <= 2 * N + 1; ++X)
        for (int Y = 0; Y <= 2 * N + 1; ++Y)
            if (abs(Cost[X][Y]) > SolutionMax)
                Cost[X][Y] = Cost[X][Y] < 0 ? -oo : oo;
    SolutionCost = MaximumFlow();
}

void Read() {
    assert(freopen("adapost.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    for (int i = 1; i <= 2 * N; ++i)
        assert(scanf("%lf %lf", &Points[i].x, &Points[i].y) == 2);
}

void Print() {
    assert(freopen("adapost.out", "w", stdout));
    printf("%.5lf %.5lf\n", SolutionMax, SolutionCost);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}