提出 #5764937

ソースコード 拡げる

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author izban
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;

#ifdef HOME
#define db(x) { cerr << #x << " = " << x << endl; }
#define db2(x, y) { cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl; }
#define db3(x, y, z) { cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")" << endl; }
#define dbv(a) { cerr << #a << " = "; for (auto xxx: a) cerr << xxx  << " "; cerr << endl; }
#else
#define db(x) ;
#define db3(x, y, z) ;
#define db2(x, y) ;
#define dbv(a) ;
#endif

#define sz(a)  (int)(a).size()
#define all(a) (a).begin(),a.end()
#define pw(x)  (1LL << (x))


// Push-Relabel implementation of the cost-scaling algorithm
// Runs in O( <max_flow> * log(V * max_edge_cost)) = O( V^2 E * log(V * C))
// Really fast in practice, like O(V * E), so 3e4 edges are fine.
// Operates on integers, costs are multiplied by N!!

// This version uses the look-ahead heuristic as described in
// "An efficient implementation of a scaling minimum-cost Flow algorithm"
// by A.V. Goldberg (1992)

template<typename flow_t = ll, typename cost_t = ll>
struct mcSFlow {
    struct Edge {
        cost_t c;
        flow_t f;
        int to, rev;

        Edge(int _to, cost_t _c, flow_t _f, int _rev) : c(_c), f(_f), to(_to), rev(_rev) {}
    };

    static constexpr cost_t INFCOST = numeric_limits<cost_t>::max() / 2;
    cost_t eps;
    int N, S, T;
    vector<vector<Edge> > G;
    vector<unsigned int> isq, cur;
    vector<flow_t> ex;
    vector<cost_t> h;

    mcSFlow(int _N, int _S, int _T) : eps(0), N(_N), S(_S), T(_T), G(_N) {}

    Edge add_edge(int a, int b, cost_t cost, flow_t cap) {
        assert(cap >= 0);
        assert(a >= 0 && a < N && b >= 0 && b < N);
        assert(a != b);
        cost *= N;
        eps = max(eps, abs(cost));
        G[a].emplace_back(b, cost, cap, G[b].size());
        Edge ret = G[a].back();
        G[b].emplace_back(a, -cost, 0, G[a].size() - 1);
        return ret;
    }

    void add_flow(Edge &e, flow_t f) {
        Edge &back = G[e.to][e.rev];
        if (!ex[e.to] && f)
            hs[h[e.to]].push_back(e.to);
        e.f -= f;
        ex[e.to] += f;
        back.f += f;
        ex[back.to] -= f;
    }

    vector<vector<int> > hs;
    vector<int> co;

    // fast max flow, lowest label version
    flow_t max_flow() {
        ex.assign(N, 0);
        h.assign(N, 0);
        hs.resize(2 * N);
        co.assign(2 * N, 0);
        cur.assign(N, 0);
        h[S] = N;
        ex[T] = 1;
        co[0] = N - 1;
        for (auto &e:G[S]) add_flow(e, e.f);
        if (hs[0].size())
            for (int hi = 0; hi >= 0;) {
                int u = hs[hi].back();
                hs[hi].pop_back();
                while (ex[u] > 0) { // discharge u
                    if (cur[u] == G[u].size()) {
                        h[u] = 1e9;
                        for (unsigned int i = 0; i < G[u].size(); ++i) {
                            auto &e = G[u][i];
                            if (e.f && h[u] > h[e.to] + 1) {
                                h[u] = h[e.to] + 1;
                                cur[u] = i;
                            }
                        }
                        if (++co[h[u]], !--co[hi] && hi < N)
                            for (int i = 0; i < N; ++i) {
                                if (hi < h[i] && h[i] < N) {
                                    --co[h[i]];
                                    h[i] = N + 1;
                                }
                            }
                        hi = h[u];
                    } else if (G[u][cur[u]].f && h[u] == h[G[u][cur[u]].to] + 1) {
                        add_flow(G[u][cur[u]], min(ex[u], G[u][cur[u]].f));
                    } else ++cur[u];
                }
                while (hi >= 0 && hs[hi].empty()) --hi;
            }
        return -ex[S];
    }

    // begin min cost flow
    bool look_ahead(int u) {
        if (ex[u]) return false;
        cost_t newHeight = h[u] - N * eps;
        for (auto const &e:G[u]) {
            if (e.f == 0) continue;
            if (h[u] + e.c - h[e.to] < 0) return false; // outgoing admissible arc
            else newHeight = max(newHeight, h[e.to] - e.c); // try to make arc admissible
        }
        h[u] = newHeight - eps;
        return true;
    }

    void push(Edge &e, flow_t amt) {
        if (e.f < amt) amt = e.f;
        e.f -= amt;
        ex[e.to] += amt;
        G[e.to][e.rev].f += amt;
        ex[G[e.to][e.rev].to] -= amt;
    }

    void relabel(int vertex) {
        cost_t newHeight = -INFCOST;
        for (unsigned int i = 0; i < G[vertex].size(); ++i) {
            Edge const &e = G[vertex][i];
            if (e.f && newHeight < h[e.to] - e.c) {
                newHeight = h[e.to] - e.c;
                cur[vertex] = i;
            }
        }
        h[vertex] = newHeight - eps;
    }

    static constexpr int scale = 2;

    template<bool use_look_ahead = true>
    pair<flow_t, cost_t> minCostMaxFlow() {
        cost_t retCost = 0;
        for (int i = 0; i < N; ++i)
            for (Edge &e:G[i])
                retCost += e.c * (e.f);
        // remove this for circulation
        flow_t retFlow = max_flow();
        h.assign(N, 0);
        ex.assign(N, 0);
        isq.assign(N, 0);
        cur.assign(N, 0);
        stack<int> q;
        for (; eps; eps >>= scale) {
            fill(cur.begin(), cur.end(), 0);
            for (int i = 0; i < N; ++i)
                for (auto &e:G[i])
                    if (h[i] + e.c - h[e.to] < 0 && e.f)
                        push(e, e.f);
            for (int i = 0; i < N; ++i) {
                if (ex[i] > 0) {
                    q.push(i);
                    isq[i] = 1;
                }
            }
            while (!q.empty()) {
                int u = q.top();
                q.pop();
                isq[u] = 0;
                while (ex[u] > 0) {
                    if (cur[u] == G[u].size())
                        relabel(u);
                    for (unsigned int &i = cur[u], max_i = G[u].size(); i < max_i; ++i) {
                        Edge &e = G[u][i];
                        if (e.f == 0) continue;
                        if (h[u] + e.c - h[e.to] < 0) {
                            if (use_look_ahead && look_ahead(e.to)) {
                                --i;
                                continue;
                            }
                            push(e, ex[u]);
                            if (isq[e.to] == 0) {
                                q.push(e.to);
                                isq[e.to] = 1;
                            }
                            if (ex[u] == 0) break;
                        }
                    }
                }
            }
            if (eps > 1 && eps >> scale == 0) {
                eps = 1 << scale;
            }
        }
        for (int i = 0; i < N; ++i) {
            for (Edge &e:G[i]) {
                retCost -= e.c * (e.f);
            }
        }
        return make_pair(retFlow, retCost / 2 / N);
    }

    flow_t getFlow(Edge const &e) {
        return G[e.to][e.rev].f;
    }
};

class D {
public:
    void solve(std::istream &in, std::ostream &out) {
        ios_base::sync_with_stdio(0);
        in.tie(0);

        int n;
        struct pt {
            int x, y, k;
        };
        in >> n;
        vector<pt> a(n), b(n);
        for (int i = 0; i < n; i++) {
            in >> a[i].x >> a[i].y >> a[i].k;
        }
        for (int i = 0; i < n; i++) {
            in >> b[i].x >> b[i].y >> b[i].k;
        }

        mcSFlow<ll, ll> g(1 + n + n + 1, 0, 1 + n + n);
        for (int i = 0; i < n; i++) {
            g.add_edge(0, 1 + i, 0, a[i].k);
            g.add_edge(1 + n + i, 1 + n + n, 0, b[i].k);
        }
        auto dist = [&](const pt &p1, const pt &p2) {
            return (ll) abs(p1.x - p2.x) + (ll) abs(p1.y - p2.y);
        };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g.add_edge(1 + i, 1 + n + j, -dist(a[i], b[j]), 10);
            }
        }
        out << -g.minCostMaxFlow().second << endl;
    }
};


int main() {
    D solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}

提出情報

提出日時
問題 D - Manhattan Max Matching
ユーザ izban
言語 C++14 (GCC 5.4.1)
得点 1200
コード長 8796 Byte
結果 AC
実行時間 3033 ms
メモリ 50816 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1200 / 1200
結果
AC × 3
AC × 36
セット名 テストケース
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, sample-01.txt, sample-02.txt, sample-03.txt
ケース名 結果 実行時間 メモリ
01-01.txt AC 1 ms 256 KiB
01-02.txt AC 889 ms 48768 KiB
01-03.txt AC 947 ms 48768 KiB
01-04.txt AC 950 ms 50816 KiB
01-05.txt AC 998 ms 48768 KiB
01-06.txt AC 788 ms 48768 KiB
01-07.txt AC 1027 ms 48768 KiB
01-08.txt AC 1137 ms 48768 KiB
01-09.txt AC 1076 ms 48768 KiB
01-10.txt AC 932 ms 48768 KiB
01-11.txt AC 979 ms 50816 KiB
01-12.txt AC 872 ms 48768 KiB
01-13.txt AC 957 ms 48768 KiB
01-14.txt AC 785 ms 48768 KiB
01-15.txt AC 1053 ms 48768 KiB
01-16.txt AC 2981 ms 48768 KiB
01-17.txt AC 2937 ms 50816 KiB
01-18.txt AC 1195 ms 48768 KiB
01-19.txt AC 937 ms 48768 KiB
01-20.txt AC 930 ms 48768 KiB
01-21.txt AC 1086 ms 48768 KiB
01-22.txt AC 662 ms 48768 KiB
01-23.txt AC 917 ms 48768 KiB
01-24.txt AC 1216 ms 48768 KiB
01-25.txt AC 1155 ms 48768 KiB
01-26.txt AC 1142 ms 48768 KiB
01-27.txt AC 1007 ms 48768 KiB
01-28.txt AC 1013 ms 48768 KiB
01-29.txt AC 1014 ms 50816 KiB
01-30.txt AC 1226 ms 48768 KiB
01-31.txt AC 970 ms 48768 KiB
01-32.txt AC 3033 ms 48768 KiB
01-33.txt AC 2889 ms 50816 KiB
sample-01.txt AC 1 ms 256 KiB
sample-02.txt AC 1 ms 256 KiB
sample-03.txt AC 1 ms 256 KiB