Cod sursa(job #2507736)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 10 decembrie 2019 19:24:31
Problema Adapost Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

const int NMax = 800, oo = 2e9;

double X[NMax + 5], Y[NMax + 5], Dist[NMax + 5][NMax + 5], Cost[NMax + 5];
int N, TT[NMax + 5], F[NMax + 5][NMax + 5], Sink, Sol, C[NMax + 5][NMax + 5];
bool InQ[NMax + 5];

vector <int> G[NMax + 5];
queue <int> Q;

double Euclid(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool BellmanFord()
{
    for(int i = 0; i <= Sink; i++)
        Cost[i] = oo, TT[i] = -1, InQ[i] = false;

    Q.push(0), Cost[0] = 0, InQ[0] = true;

    while(!Q.empty())
    {
        int Node = Q.front(); Q.pop(), InQ[Node] = false;

        for(int Next : G[Node])
            if(F[Node][Next] != C[Node][Next] && Cost[Node] + Dist[Node][Next] < Cost[Next])
            {
                Cost[Next] = Cost[Node] + Dist[Node][Next];
                TT[Next] = Node;

                if(InQ[Next] == false)
                    Q.push(Next), InQ[Next] = true;
            }
    }
    return (Cost[Sink] != oo);
}

double Flow(double DistMax)
{
    for(int i = 0; i <= Sink; i++)
    {
        G[i].clear();

        for(int j = 0; j <= Sink; j++)
            F[i][j] = 0;
    }

    for(int i = 1; i <= N; i++)
        G[0].push_back(i), G[i].push_back(0), C[0][i] = 1;

    for(int i = N + 1; i <= 2 * N; i++)
        G[i].push_back(Sink), G[Sink].push_back(i), C[i][Sink] = 1;

    for(int i = 1; i <= N; i++)
        for(int j = N + 1; j < Sink; j++)
        {
            C[i][j] = 1;

            if(Dist[i][j] <= DistMax)
                G[i].push_back(j), G[j].push_back(i);
        }
    double Ans = 0;
    int FluxMax = 0;

    while(BellmanFord())
    {
        int Fmin = oo;

        for(int i = Sink; TT[i] != -1; i = TT[i])
            Fmin = min(Fmin, C[TT[i]][i] - F[TT[i]][i]);

        for(int i = Sink; TT[i] != -1; i = TT[i])
            F[TT[i]][i] += Fmin, F[i][TT[i]] -= Fmin;

        Ans += Fmin * Cost[Sink];
        FluxMax += Fmin;
    }
    return ((FluxMax == N) ? Ans : -1);
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> X[i] >> Y[i];

    for(int i = N + 1; i <= 2 * N; i++)
    {
        double x, y;
        fin >> x >> y;

        for(int soldier = 1; soldier <= N; soldier++)
        {
            Dist[soldier][i] = Euclid(x, y, X[soldier], Y[soldier]);
            Dist[i][soldier] = -Dist[soldier][i];
        }
    }
    Sink = 2 * N + 1;

    for(int step = (1 << 24); step > 0; step >>= 1)
    {
        if(Flow((Sol + step) / 10000.0) == -1)
            Sol += step;
    }
    fout << fixed << setprecision(4) << (Sol + 1) / 10000.0 << " " << Flow((Sol + 1) / 10000.0) << '\n';

    fin.close();
    fout.close();

    return 0;
}