Cod sursa(job #990627)

Utilizator poptibiPop Tiberiu poptibi Data 28 august 2013 19:01:07
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.21 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;

#define EPS 1e-4
#define Nmax 810
#define pb push_back

int N, Flow[Nmax][Nmax], Cap[Nmax][Nmax], Source, Sink, Father[Nmax], L[Nmax], R[Nmax];
double Cost[Nmax][Nmax], AnsFlow, AnsDist, Dist[Nmax];
double X[Nmax], Y[Nmax], XA[Nmax], YA[Nmax];
vector<int> G[Nmax], GC[Nmax];
bool Used[Nmax], InQueue[Nmax];

bool BellmanFord()
{
    for(int i = Source; i <= Sink; ++ i)
        Dist[i] = 1.0 * 0x3f3f3f3f, Father[i] = 0;

    Dist[Source] = 0;
    queue<int> Q;
    Q.push(Source);

    while(!Q.empty())
    {
        int Node = Q.front();
        Q.pop();
        if(Node == Sink) return 1;
        InQueue[Node] = 0;
        for(vector<int> :: iterator it = G[Node].begin(); it != G[Node].end(); ++ it)
            if(Cap[Node][*it] > Flow[Node][*it] && Dist[*it] > Dist[Node] + Cost[Node][*it])
            {
                Dist[*it] = Dist[Node] + Cost[Node][*it];
                Father[*it] = Node;
                if(!InQueue[*it])
                    InQueue[*it] = 1, Q.push(*it);
            }
    }
    return Dist[Sink] != 1.0 * 0x3f3f3f3f;
}

void MinCostMaxFlow()
{
    double MaxFlow = 0.0;
    while(BellmanFord())
    {
        int MinFlow = 0x3f3f3f3f;
        for(int Node = Sink; Node != Source; Node = Father[Node])
            MinFlow = min(MinFlow, Cap[Father[Node]][Node] - Flow[Father[Node]][Node]);

        for(int Node = Sink; Node != Source; Node = Father[Node])
        {
            Flow[Father[Node]][Node] += MinFlow;
            Flow[Node][Father[Node]] -= MinFlow;
        }
        MaxFlow += 1.0 * MinFlow * Dist[Sink];
    }
    AnsFlow = MaxFlow;
}

int PairUp(int Node)
{
    if(Used[Node]) return 0;
    Used[Node] = 1;
    for(vector<int> :: iterator it = GC[Node].begin(); it != GC[Node].end(); ++ it)
        if(!R[*it] || PairUp(R[*it]))
        {
            L[Node] = *it;
            R[*it] = Node;
            return 1;
        }
    return 0;
}

int MaxMatching()
{
    int Ans = 0, OK = 1;
    while(OK)
    {
        OK = 0;
        memset(Used, 0, sizeof(Used));
        for(int i = 1; i <= N; ++ i)
            if(!L[i] && PairUp(i))
                Ans ++, OK = 1;
    }
    return Ans;
}

double Distance(int i, int j)
{
    return sqrt((X[i] - XA[j]) * (X[i] - XA[j]) + (Y[i] - YA[j]) * (Y[i] - YA[j]));
}

void BuildGraph(double MaxDist)
{
    for(int i = Source; i <= Sink; ++ i)
    {
        G[i].clear();
        GC[i].clear();
        L[i] = R[i] = Dist[i] = 0;
    }
    for(int i = Source; i <= Sink; ++ i)
        for(int j = Source; j <= Sink; ++ j)
            Cap[i][j] = Flow[i][j] = Cost[i][j] = 0;

    Source = 0;
    Sink = 2 * N + 1;
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            if(Distance(i, j) <= MaxDist)
            {
                G[i].pb(j + N);
                G[j + N].pb(i);
                GC[i].pb(j);
                Cap[i][j + N] = 1;
                Cost[i][j + N] = Distance(i, j);
                Cost[j + N][i] = -Cost[i][j + N];
            }
    for(int i = 1; i <= N; ++ i)
    {
        Cap[Source][i] = 1;
        Cap[i + N][Sink] = 1;
        G[Source].pb(i); G[i].pb(Source);
        G[i + N].pb(Sink); G[Sink].pb(i + N);
    }
}

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

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
        scanf("%lf %lf", &X[i], &Y[i]);
    for(int i = 1; i <= N; ++ i)
        scanf("%lf %lf", &XA[i], &YA[i]);

    double Left = 0.0, Right = 0.0, Mid;
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            Right = max(Right, Distance(i, j));

    Right += EPS;
    int Steps = 0;
    while(Steps <= 50)
    {
        Mid = (Left + Right) / 2;
        BuildGraph(Mid);
        int Matching = MaxMatching();
        if(Matching < N) Left = Mid;
        else
        {
            AnsDist = Mid;
            MinCostMaxFlow();
            Right = Mid;
        }
        Steps ++;
    }

    printf("%f %f\n", AnsDist, AnsFlow);
    return 0;
}