Cod sursa(job #1015776)

Utilizator freak93Adrian Budau freak93 Data 25 octombrie 2013 09:20:40
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <limits>
#include <stdexcept>

using namespace std;

typedef pair<double, double> Soldier, Shelter;

const double kInfinite = 1e50;

const double kEpsilon = 1e-6;

int cmp(double a, double b) {
    if (a + kEpsilon < b)
        return -1;
    if (b + kEpsilon < a)
        return 1;
    return 0;
}

bool equal(double a, double b) {
    return cmp(a, b) == 0;
}

class SimpleGraph {
  public:
    SimpleGraph(int size):
            size_(size),
            edges_(size) {
    }

    void addEdge(int from, int to) {
        edges_[from].push_back(to);
    }

    bool didInvertChain(int from, int to) {
        queue<int> Q;
        Q.push(from);

        vector<int> parent(size_, -1);
        parent[from] = from;
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            if (node == to)
                break;

            for (auto &next : edges_[node])
                if (parent[next] == -1) {
                    parent[next] = node;
                    Q.push(next);
                }
        }

        if (parent[to] == -1)
            return false;
        for (int node = to; node != from; node = parent[node]) {
            vector<int> &where = edges_[parent[node]];
            where.erase(find(where.begin(), where.end(), node));
            edges_[node].push_back(parent[node]);
        }
        return true;
    }

    const vector<int>& edges(int node) const {
        return edges_[node];
    }

  private:
    int size_;
    vector< vector<int> > edges_;
};

class BipartiteGraph {
  public:
    BipartiteGraph(int size_l, int size_r):
            size_l_(size_l),
            size_r_(size_r),
            edges_(size_l) {
    }

    void addEdge(int from, int to, double distance) {
        edges_[from].push_back({to, distance});
    }

    double minimumWeightMatching() const {
        if (size_l_ != size_r_)
            throw new runtime_error("Graph is not regular");

        int steps = size_l_;

        vector<double> costLeft(size_l_, 0), costRight(size_r_, 0);
        vector<int> leftMatch(size_l_, -1), rightMatch(size_r_, -1);

        while (steps--) {
            vector<double> tillEdge(size_r_, kInfinite);
            vector<int> typeLeft(size_l_, 0), typeRight(size_r_, 0);

            for (int i = 0; i < size_l_; ++i)
                if (leftMatch[i] != -1)
                    typeLeft[i] |= Type::matched;
            for (int i = 0; i < size_r_; ++i)
                if (rightMatch[i] != -1)
                    typeRight[i] |= Type::matched;

            queue<int> Q;
            for (int i = 0; i < size_l_; ++i)
                if (~typeLeft[i] & Type::matched) {
                    typeLeft[i] |= Type::chosen;
                    Q.push(i);
                }
            auto updateRight = [&](int node) {
                typeRight[node] |= Type::chosen;
                tillEdge[node] = kInfinite;

                // go left if possible
                if (typeRight[node] & Type::matched) {
                    int leftNode = rightMatch[node];
                    typeLeft[leftNode] |= Type::chosen;
                    Q.push(leftNode);
                }
            };

            do {
                while (!Q.empty()) {
                    int node = Q.front();
                    Q.pop();

                    // pass the graph
                    for (auto &next : edges_[node]) {
                        if ((~typeRight[next.to]) & Type::chosen) 
                             if (equal(costLeft[node] + costRight[next.to], next.distance))
                                 if (next.to != leftMatch[node])
                                    updateRight(next.to);

                        if (~typeRight[next.to] & Type::chosen)
                            tillEdge[next.to] = min(tillEdge[next.to],
                                                    next.distance - costLeft[node] - costRight[next.to]);
                    }
                }

                int nextChange = min_element(tillEdge.begin(), tillEdge.end()) - tillEdge.begin();
                double change = tillEdge[nextChange];
                // we're still stuck here, let's extend
                for (int i = 0; i < size_l_; ++i)
                    if (typeLeft[i] & Type::chosen)
                        costLeft[i] += change;
                for (int i = 0; i < size_r_; ++i)
                    if (typeRight[i] & Type::chosen)
                        costRight[i] -= change;
                    else if (!equal(tillEdge[i], kInfinite))
                        tillEdge[i] -= change;
                if (~typeRight[nextChange] & Type::matched)
                    break;
                updateRight(nextChange);
            } while (true);

            // yey we got a new edge
            // and luckily the queue is empty
            vector<int> fromRight(size_r_, -1);
            for (int i = 0; i < size_l_; ++i)
                if (~typeLeft[i] & Type::matched) {
                    Q.push(i);
                }

            while (!Q.empty()) {
                int node = Q.front();
                Q.pop();
                for (auto &next : edges_[node])
                    if (fromRight[next.to] == -1 && equal(costLeft[node] + costRight[next.to], next.distance)) {
                        fromRight[next.to] = node;
                        if (typeRight[next.to] & Type::matched)
                            Q.push(rightMatch[next.to]);
                    }
            }

            // we're almost done, let's do this
            for (int i = 0; i < size_r_; ++i)
                if (fromRight[i] != -1 && ~typeRight[i] & Type::matched) {
                    for (int node = i; node != -1; ) {
                        rightMatch[node] = fromRight[node];
                        int next = leftMatch[rightMatch[node]];
                        leftMatch[rightMatch[node]] = node;
                        node = next;
                    }
                }
        }

        // and lucky for us the sum of y's is the answer
        double answer = 0;
        for (int i = 0; i < size_l_; ++i)
            answer += costLeft[i] + costRight[i];
        return answer;
    }

  private:
    class Edge {
      public:
        Edge(int _to, double _distance):
                to(_to), distance(_distance) {}
        int to;
        double distance;
    };

    struct Type {
        static const int matched = 1;
        static const int chosen = 2;
    };

    int size_l_, size_r_;
    vector< vector<Edge> > edges_;
};

int main() {
    ifstream cin("adapost.in");
    ofstream cout("adapost.out");

    int N; cin >> N;

    vector<Soldier> A(N);
    vector<Shelter> B(N);

    for (int i = 0; i < N; ++i)
        cin >> A[i].first >> A[i].second;
    for (int i = 0; i < N; ++i)
        cin >> B[i].first >> B[i].second;

    vector< vector<double> > distance(N, vector<double>(N, 0));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            distance[i][j] = sqrt((A[i].first - B[j].first) * (A[i].first - B[j].first) + 
                                  (A[i].second - B[j].second) * (A[i].second - B[j].second));

    vector< pair<int, int> > pairs(N * N);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            pairs[i * N + j] = {i, j};
    sort(pairs.begin(), pairs.end(), [&](pair<int, int> A, pair<int, int> B) {
        return distance[A.first][A.second] < distance[B.first][B.second];
    });

    SimpleGraph G(2 * N + 2);
    for (int i = 0; i < N; ++i) {
        G.addEdge(2 * N, i); // source to soldier
        G.addEdge(i + N, 2 * N + 1); // shelter to sink
    }

    int matches = 0;

    double maxDistance = 0;
    for (auto &pair: pairs) {
        G.addEdge(pair.first, pair.second + N);
        while (G.didInvertChain(2 * N, 2 * N + 1)) // we invert a chain between the source and sink
                                                   // at most one new chain can appear when we add an edge
            ++matches;
        if (matches == N) {
            maxDistance = distance[pair.first][pair.second];
            break;
        }
    }

    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(5);
    cout << maxDistance << " ";

    BipartiteGraph M(N, N);
    for (int i = 0; i < N; ++i) {
        for (auto &next : G.edges(i))
            if (next != 2 * N) // if it's not a source edge
                M.addEdge(i, next - N, distance[i][next - N]);
        for (auto &prev : G.edges(i + N))
            if (prev != 2 * N + 1) // if it's not a sink edge
                M.addEdge(prev, i, distance[prev][i]);
    }

    cout << M.minimumWeightMatching() << "\n";
}