Cod sursa(job #2377336)

Utilizator silviu982001Borsan Silviu silviu982001 Data 9 martie 2019 19:53:02
Problema Adapost 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.46 kb
#include <bits/stdc++.h>

#define NMAX 810
#define SMAX 405
#define INF 1e9

using namespace std;

unsigned long n,m,S,D, p[NMAX];
vector<pair<double, double>> adapost, soldat;
vector<pair<double, pair<int, int>>> distante;
int ll[SMAX], lr[SMAX];
bitset<SMAX> viz;
vector<int> G[SMAX];
vector<unsigned long> V[NMAX];
int C[NMAX][NMAX], F[NMAX][NMAX];
double Cost[NMAX][NMAX], oldDist[NMAX], result;


inline double sqr(double x)
{
    return pow(x,2);
}

bool cupleaza(int nod)
{
    if (viz[nod])
        return false;
    viz[nod] = 1;
    for (int vec : G[nod])
        if (!lr[vec])
        {
            ll[nod] = vec;
            lr[vec] = nod;
            return true;
        }
    for(int nd : G[nod])
        if(cupleaza(lr[nd]))
        {
            ll[nod]=nd;
            lr[nd]=nod;
            return true;
        }
    return false;
}


bool cuplaj(unsigned long poz)
{
    memset(ll, 0, sizeof(ll));
    memset(lr, 0, sizeof(lr));
    unsigned long nods = 0;
    bool found;
    for (unsigned long i = 0; i <= poz; ++i)
        G[distante[i].second.first].push_back(distante[i].second.second);
    do
    {
        found = false;
        viz.reset();
        for (unsigned long i = 1; i <= n; ++i)
            if (!ll[i])
                if (cupleaza(i))
                {
                    ++nods;
                    found = true;
                }
    }
    while (found);
    for (unsigned long i = 0; i <= n; ++i)
        G[i].resize(0);
    return (nods == n);
}

void belmanFord()
{
    for (unsigned long i = 0; i <= D; ++i)
        oldDist[i] = INF;

    oldDist[S] = 0;
    queue<unsigned long> Q;
    bitset<NMAX> inQ;
    inQ.reset();
    for (Q.push(S), inQ[S] = 1; !Q.empty();)
    {
        unsigned long nod = Q.front();
        Q.pop();
        inQ[nod] = 0;
        for (unsigned long vec : V[nod])
            if (C[nod][vec] > 0)
            {
                double d = oldDist[nod] + Cost[nod][vec];
                if (oldDist[vec] > d)
                {
                    oldDist[vec] = d;
                    if (!inQ[vec])
                    {
                        Q.push(vec);
                        inQ[vec]=1;
                    }
                }
            }
    }
}

bool dijkastra()
{
    priority_queue<pair<double, unsigned long>, vector<pair<double, unsigned long>>, greater<pair<double, unsigned long>>> H;
    memset(p, 0, sizeof(p));
    double cDist[NMAX], realDist[NMAX];
    for (unsigned long i = S; i <= D; ++i)
        cDist[i] = INF;
    cDist[S] = realDist[S] = 0;

    H.push({0, S});

    while (!H.empty())
    {
        double d = H.top().first;
        unsigned long nod = H.top().second;

        H.pop();

        if (cDist[nod] != d)
            continue;

        for (unsigned long vec : V[nod])
        {
            if (C[nod][vec] > F[nod][vec])
            {
                double dst = d + Cost[nod][vec] + oldDist[nod] - oldDist[vec];

                if (dst < cDist[vec])
                {
                    cDist[vec] = dst;
                    realDist[vec] = realDist[nod] + Cost[nod][vec];
                    p[vec] = nod;
                    H.push({dst, vec});
                }
            }
        }
    }

    if (p[D] == 0)
        return false;

    memcpy(oldDist, realDist, sizeof(oldDist));

    int flow = INT_MAX;
    for(unsigned long nod = D; nod != S; nod = p[nod])
        flow = min(flow, C[p[nod]][nod]-F[p[nod]][nod]);

    for (unsigned long nod = D; nod != S; nod = p[nod])
    {
        F[p[nod]][nod] += flow;
        F[nod][p[nod]] -= flow;
    }

    result += flow * realDist[D];


    return true;
}


int main()
{
    ifstream fin("adapost.in");
    fin >> n;
    double x, y;
    for (unsigned long i = 0; i < n; ++i)
    {
        fin >> x >> y;
        soldat.push_back({x,y});
    }
    for (unsigned long i = 0; i < n; ++i)
    {
        fin >> x >> y;
        adapost.push_back({x,y});
    }
    fin.close();
    for (unsigned long i = 0; i < n; ++i)
        for (unsigned long j = 0; j < n; ++j)
        {
            double d = sqrt(sqr(soldat[i].first - adapost[j].first) + sqr(soldat[i].second - adapost[j].second));
            distante.push_back({d, {i+1, j+1}});
        }
    sort(distante.begin(), distante.end());
    unsigned long st = 0, dr = distante.size()-1;
    while (st <= dr)
    {
        unsigned long mij = (st+dr)/2;
        if (cuplaj(mij))
        {
            m = mij;
            dr = mij-1;
        }
        else st = mij+1;
    }

    S = 1;
    D = 2*n+2;
    for (unsigned long i = 2; i <= n+1; ++i)
    {
        V[S].push_back(i);
        V[i].push_back(S);
        C[S][i] = 1;
    }
    for (unsigned long i = n+2; i <= D; ++i)
    {
        V[D].push_back(i);
        V[i].push_back(D);
        C[i][D] = 1;
    }
    for (unsigned long i = 0; i <= m; ++i)
    {
        unsigned long xx = distante[i].second.first+1;
        unsigned long yy = distante[i].second.second+n+1;
        C[xx][yy] = 1;
        Cost[xx][yy] = distante[i].first;
        Cost[yy][xx] = -distante[i].first;
        V[xx].push_back(yy);
        V[yy].push_back(xx);
    }

    belmanFord();

    for(;dijkastra(););

    ofstream fout("adapost.out");
    fout.setf(ios::fixed, ios::floatfield);
    fout.precision(5);
    fout << distante[m].first << " " << result;
    fout.close();

    return 0;
}