Cod sursa(job #830773)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 decembrie 2012 17:47:56
Problema Adapost Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <cstdio>
#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];
queue<int> Q;

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, const double MaxCost) {
    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 (Cost[X][*Y] <= MaxCost && 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;
}

inline void InitFlow() {
    FlowMinCost = 0.0;
    for (int X = 0; X <= 2 * N + 1; ++X)
        for (int Y = 0; Y <= 2 * N + 1; ++Y)
            Flow[X][Y] = 0;
}

int MaximumFlow(const double MaxCost) {
    InitFlow();
    int MaxFlow = 0;
    while (BellmanFord(Source, Sink, MaxCost)) {
        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, FlowMinCost += CurrentFlow * Distance[Sink];
    }
    return MaxFlow;
}

void Solve() {
    BuildGraph();
    double Left = 0, Right = oo;
    while (Right - Left > Eps) {
        double Middle = 0.5 * (Left + Right);
        if (MaximumFlow(Middle) >= N)
            Right = Middle - Eps, SolutionMax = Middle;
        else
            Left = Middle + Eps;
    }
    assert(MaximumFlow(SolutionMax) >= N);
    SolutionCost = FlowMinCost;
}

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;
}