Cod sursa(job #2798592)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:38:14
Problema Adapost Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.94 kb
#include <bits/stdc++.h>

#define x first
#define y second
#define INF 1000000
#define source 0

using namespace std;

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

short capacity[1024][1024], flow[1024][1024], N, T[1024], Left[1024], Right[1024], destination;
double solution, mainSolution, cost[1024][1024], D[1024], stanga = 1000000, dreapta;
pair< double,  double> soldat[1024], adapost[1024];
bitset<1024>v;

vector <short> L[1024];
queue  <short> Q;

inline bool cuplaj(const short &node)
{
    v[node] = 1;

    for(short i = 0; i < L[node].size(); i ++)
    {
        if( !Right[ L[node][i] ])
        {
            Left[ node ] = L[node][i];
            Right[ L[node][i] ] = node;
            return true;
        }
    }

    for(short i = 0; i < L[node].size(); i ++)
    {
        if( !v[ Right[ L[node][i] ] ] && cuplaj( Right[ L[node][i] ] ))
        {
            Left[ node ] = L[node][i];
            Right[ L[node][i] ] = node;
            return true;
        }
    }

    return false;
}

inline bool verif(const double &maxMuchie)
{
    memset(Left, 0, sizeof(Left));
    memset(Right, 0, sizeof(Right));

    for(short i = 1; i <= N; i ++)
    {
        L[i].clear();
    }

    for(short i = 1; i <= N; i ++)
    {
        for(short j = 1; j <= N; j ++)
        {
            if(cost[i][N + j] - maxMuchie < 0.000001)
            {
                L[i].push_back(j);
            }
        }
    }

    bool ok = true;
    short cardCuplaj = 0;

    while(ok)
    {
        ok = false;
        v.reset();

        for(short i = 1; i <= N; i ++)
        {
            if( !Left[i]  && cuplaj(i))
            {
                cardCuplaj ++;
                ok = true;
            }
        }
    }

    return cardCuplaj == N;

}

inline bool bellmanFord()
{
    for(short i = 1; i <= destination; i ++)
    {
        D[i] = INF;
        v[i] = 0;
    }

    Q.push(source);

    while(!Q.empty())
    {
        short node = Q.front();
        v[node] = 0;
        Q.pop();

        for(short i = 0; i < L[node].size(); i ++)
        {
            short neighbour = L[node][i];

            if(D[neighbour] > D[node] + cost[node][neighbour] && capacity[node][neighbour] > flow[node][neighbour])
            {
                D[neighbour] = D[node] + cost[node][neighbour];
                T[neighbour] = node;

                if(v[neighbour] == 0)
                {
                    v[neighbour] = 1;
                    Q.push(neighbour);
                }
            }
        }
    }

    return D[destination] != INF;
}

inline void maxFlow(const double &maxMuchie)
{
    for(short i = 0; i <= 801; i ++)
    {
        L[i].clear();
    }

    for(short i = 1; i <= N; i ++)
    {
        L[source].push_back(i);
        L[i].push_back(source);
        capacity[source][i] = 1;

        L[destination].push_back(i + N);
        L[i + N].push_back(destination);
        capacity[i + N][destination] = 1;
    }

    for(short i = 1; i <= N; i ++)
    {
        for(short j = 1; j <= N; j ++)
        {
            if(  cost[i][N + j] - maxMuchie < 0.000001 )
            {
                L[i].push_back(N + j);
                L[N + j].push_back(i);

                capacity[i][N + j] = 1;
            }
        }
    }

    while(bellmanFord())
    {
        short Fmin = INF;

        short x = destination;

        while(x > source)
        {
            //Fmin = min(Fmin, capacity[ T[x] ][x] - flow[ T[x] ][x]);
            if(Fmin > capacity[ T[x] ][x] - flow[ T[x] ][x])
            {
                Fmin = capacity[ T[x] ][x] - flow[ T[x] ][x];
            }
            x = T[x];
        }

        x = destination;

        while(x > source)
        {
            flow[ T[x] ][x] += Fmin;
            flow[x][ T[x] ] -= Fmin;
            x = T[x];
        }

        solution += D[destination] * Fmin;
    }
}

int main()
{
    fin >> N;

    for(short i = 1; i <= N; i ++)
    {
        fin >> soldat[i].x >> soldat[i].y;
    }

    for(short i = 1; i <= N; i ++)
    {
        fin >> adapost[i].x >> adapost[i].y;
    }

    for(short i = 1; i <= N; i ++)
    {
        for(short j = 1; j <= N; j ++)
        {
            cost[i][N + j] = sqrt( (adapost[j].y - soldat[i].y) * (adapost[j].y - soldat[i].y) +
                            (adapost[j].x - soldat[i].x) * (adapost[j].x - soldat[i].x) );

            cost[N + j][i] = -cost[i][N + j];
            dreapta = max(dreapta, cost[i][N + j]);

        }
    }

    stanga = 0;
    destination = 2 * N + 1;

    for (short i = 1; i <= 21; i++) {

        double middle = (stanga + dreapta) / 2;

        if(verif(middle))
            dreapta = middle;
        else
            stanga = middle;

    }

    maxFlow(dreapta);

    fout << setprecision(5) << fixed << dreapta << " " << solution;


    return 0;
}