Cod sursa(job #1207296)

Utilizator andreiiiiPopa Andrei andreiiii Data 12 iulie 2014 18:42:57
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.61 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>

using namespace std;

const int Nmax = 805, INF = 0x3f3f3f3f;
const int Source = 0, Destination = 803;

class Point {
public:
    double x, y;

    Point(const double _x = 0, const double _y = 0):
        x(_x),
        y(_y) {}
};

class Edge {
public:
    int from, to;
    double cost;

    Edge(const int _from = 0, const int _to = 0, const double _cost = 0):
        from(_from),
        to(_to),
        cost(_cost) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
};

Point Points[Nmax];
int N, Ans;

void Read()
{
    ifstream fin("adapost.in");

    fin >> N;
    for (int i = 1; i <= 2 * N; i++)
        fin >> Points[i].x >> Points[i].y;

    fin.close();
}

double Dist(const Point a, const Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Edge Edges[Nmax * Nmax];

vector<int> G[Nmax];

int L[Nmax], R[Nmax];
bitset<Nmax> V;

void BuildMatchingNetwork(const int T)
{
    for (int i = 1; i <= N; i++) G[i].clear();

    for (int i = 1; i <= T; i++)
    {
        G[Edges[i].from].push_back(Edges[i].to - N);
    }

    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
}

int PairUp(const int node)
{
    if (V[node]) return 0;
    V[node] = 1;

    for (const int p: G[node])
    {
        if (!R[p])
        {
            L[node] = p;
            R[p] = node;
            return 1;
        }
    }

    for (const int p: G[node])
    {
        if (PairUp(R[p]))
        {
            L[node] = p;
            R[p] = node;
            return 1;
        }
    }

    return 0;
}

int GetMatching()
{
    for (int ok = 1; ok; )
    {
        ok = 0;
        V.reset();

        for (int i = 1; i <= N; i++)
            if (!L[i])
                ok |=PairUp(i);
    }

    int ret = 0;
    for (int i = 1; i <= N; i++)
        if (L[i])
            ret++;

    return ret;
}

int C[Nmax][Nmax], F[Nmax][Nmax];
int Father[Nmax];
double Cost[Nmax][Nmax], Distt[Nmax];
bitset<Nmax> inQueue;

void AddEdge(const int from, const int to, const int cap, const double cost)
{
    G[from].push_back(to);
    C[from][to] = cap;
    Cost[from][to] = cost;

    G[to].push_back(from);
    Cost[to][from] = -cost;
}

void BuildFlowNetwork(const int T)
{
    for (int i = 1; i <= 2 * N; i++) G[i].clear();

    for (int i = 1; i <= T; i++)
        AddEdge(Edges[i].from, Edges[i].to, 1, Edges[i].cost);

    for (int i = 1; i <= N; i++)
    {
        AddEdge(Source, i, 1, 0);
        AddEdge(N + i, Destination, 1, 0);
    }
}

bool BellmanFord()
{
    queue<int> Q;
    for (int i = 1; i <= 2 * N; i++)
        Distt[i] = INF;
    Distt[Destination] = INF;

    inQueue.reset();

    for (Q.push(Source); !Q.empty(); )
    {
        const int node = Q.front();
        Q.pop();

        inQueue[node] = 0;

        for (const int p: G[node])
        {
            if (C[node][p] == F[node][p]) continue;

            if (Distt[p] > Distt[node] + Cost[node][p])
            {
                Distt[p] = Distt[node] + Cost[node][p];
                Father[p] = node;

                if (!inQueue[p])
                {
                    inQueue[p] = 1;
                    Q.push(p);
                }
            }
        }
    }

    if (Distt[Destination] < INF) return true;
    return false;
}

pair<int, double> GetFlow()
{
    int flow = 0;
    double flowcost = 0;

    while (BellmanFord())
    {
        int fmin = INF;
        for (int i = Destination; i != Source; i = Father[i])
            fmin = min(fmin, C[Father[i]][i] - F[Father[i]][i]);

        for (int i = Destination; i != Source; i = Father[i])
        {
            F[Father[i]][i] += fmin;
            F[i][Father[i]] -= fmin;
        }

        flow += fmin;
        flowcost += fmin * Distt[Destination];
    }

    return make_pair(flow, flowcost);
}

void Solve()
{
    int k = 0;
    for (int i = 1; i <= N; i++)
        for (int j = N + 1; j <= 2 * N; j++)
            Edges[++k] = Edge(i, j, Dist(Points[i], Points[j]));

    sort(Edges + 1, Edges + k + 1);

    int l = 1, r = k;

    while (l <= r)
    {
        int mid = (l + r) / 2;

        BuildMatchingNetwork(mid);
        int P = GetMatching();

        if (P < N) l = mid + 1;
        else
        {
            Ans = mid;
            r = mid - 1;
        }
    }
}

void Write()
{
    ofstream fout("adapost.out");
    BuildFlowNetwork(Ans);
    pair<int, double> P = GetFlow();

    fout << setprecision(5) << fixed;
    fout << Edges[Ans].cost << " " << P.second << "\n";

    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();
}