Cod sursa(job #1795963)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 2 noiembrie 2016 23:02:27
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.09 kb
#include <bits/stdc++.h>

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

using namespace std;

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

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

struct cmp {
    bool operator()(pair<double, int> a, pair<double, int> b) {
        return a.first > b.first;
    }
};
priority_queue<pair<double, int>, vector< pair<double, int> >, cmp> H;

vector <int> L[1024];
vector <int> G[1024];
queue  <int> Q;

class Comp {

public:

    bool operator()(const pair<int, double> &a, const pair<int, double> &b) {

        return a.second > b.second;

    }

};

priority_queue< pair<int, double>, vector< pair<int, double> >, Comp > heap;


double dist[dim], newDist[dim], dijDist[dim];

queue<int> que;
bool inQue[dim];

void bellmanFord() {

    for (int i = source; i <= destination; ++i)
        dist[i] = INF, inQue[i] = false;

    dist[source] = 0;

    queue<int> que;

    que.push(source);

    while (!que.empty()) {

        int curr = que.front();
        que.pop();

        inQue[curr] = false;

        for (int adj : L[curr]) {

            if (dist[adj] <= dist[curr] + cost[curr][adj] || capacity[curr][adj] == flow[curr][adj])
                continue;

            dist[adj] = dist[curr] + cost[curr][adj];

            if (inQue[adj])
                continue;

            inQue[adj] = true;
            que.push(adj);

        }

    }

}

bool dijkstra() {

    for (int i = source; i <= destination; ++i)
        dijDist[i] = INF, newDist[i] = INF;

    dijDist[source] = newDist[source] = 0;

    heap.push(make_pair(source, 0));

    while (!heap.empty()) {

        int curr = heap.top().first;
        double cst = heap.top().second;
        heap.pop();

        if (dijDist[curr] != cst)
            continue;

        for (int adj : L[curr]) {

            if (capacity[curr][adj] == flow[curr][adj])
                continue;

            double temp = dijDist[curr] + cost[curr][adj] + dist[curr] - dist[adj];

            if (temp < dijDist[adj]) {

                dijDist[adj] = temp;

                newDist[adj] = newDist[curr] + cost[curr][adj];

                T[adj] = curr;

                heap.push(make_pair(adj, temp));

            }

        }

    }

    memcpy(dist, newDist, sizeof dist);

    return dist[destination] != INF;

}

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

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

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

    return false;
}

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


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

    bool ok = true;
    int cardCuplaj = 0;

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

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

    return cardCuplaj == N;

}


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

    for(int 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(int i = 1; i <= N; i ++)
    {
        for(int 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;
            }
        }
    }


    bellmanFord();

    while(dijkstra())
    {
        int Fmin = INF;

        int x = destination;

        while(x > source)
        {
            Fmin = min(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 += dist[destination] * Fmin;
    }
}

int main()
{
    fin >> N;

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

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

    for(int i = 1; i <= N; i ++)
    {
        for(int 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 (int 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;
}