#194472 (C++14) No.519 アイドルユニット

提出ソース
結果

問題	No.519 アイドルユニット
ユーザー	はまやんはまやん
提出日時	2017-08-08 10:48:14
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	20,615 bytes
コンパイル時間	4,049 ms
コンパイル使用メモリ	226,352 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-12 00:09:19
合計ジャッジ時間	4,719 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	1 ms 5,248 KB
testcase_25	AC	1 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template <typename WeightType>
class MaximumWeightedMatching {
    /*
    Maximum Weighted Matching in General Graphs
    - O(n^3) time
    - O(n + m) space

    Note: each vertex is 1-indexed.
    */
public:
    using i8 = signed char;
    using i64 = long long;
    using weight_t = WeightType;
    using weight_sum_t = i64;
    struct Edge { int from, to; weight_t weight; Edge(int a, int b, weight_t c) : from(a), to(b), weight(c) {}
    Edge() {} };

private:
    enum TreeLabelNumber { INNER = -1, UNUSED = 0, OUTER = 1 };
    enum LabelNumber { SEPARATED = -2, DEFAULT = -1 };
    enum EdgeNumber { UNDEFINED = 1 << 30 };

    static constexpr weight_t INF = weight_t(1) << (sizeof(weight_t) * 8 - 2);

    struct Node { int next, from, to; };
    struct Label { int from, to; };
    struct LinkedList { int eid, next; };

    class Queue {
    public:
        Queue() {}
        Queue(int N) : que(N), qh(0), qt(0) {}
        void clear() { qh = qt = 0; }
        int* data() { return que.data(); }
        bool empty() const { return qh == qt; }
        int dequeue() { return que[qh++]; }
        void enqueue(int u) { que[qt++] = u; }
        int operator [] (int i) const { return que[i]; }
        int size() const { return qt; }

        vector<int> que;
        int qh, qt;
    };

public:
    MaximumWeightedMatching(int N, const vector<Edge>& raw_edges)
        : N(N), B((N - 1) / 2), size(N + B + 1) {

        offsets.assign(N + 2, 0);
        for (auto& e : raw_edges) {
            offsets[e.from + 1]++;
            offsets[e.to + 1]++;
        }
        rep(i, 1, N + 1) offsets[i] += offsets[i - 1];
        edges.resize(raw_edges.size() * 2);
        rep(i, 0, raw_edges.size()) {
            auto& e = raw_edges[i];
            edges[offsets[e.from]++] = { e.from, e.to, 2 * e.weight };
            edges[offsets[e.to]++] = { e.to, e.from, 2 * e.weight };
        }
        rep(i, 0, N + 1) offsets[N + 1 - i] = offsets[N - i];
        offsets[0] = 0;
    }

    weight_sum_t maximum_weighted_matching() {
        initialize();
        set_potential();
        rep(u, 1, N + 1) if (!mate[u]) {
            for (int s = 0; !augmented(u, s); s = adjust_dual_solutions());
            fix_blossom_bases();
            clear_label();
        }
        weight_sum_t ret = 0;
        rep(u, 1, N + 1) if (mate[u] > u) {
            weight_t max_w = 0;
            rep(eid, offsets[u], offsets[u + 1]) if (edges[eid].to == mate[u]) {
                max_w = max(max_w, edges[eid].weight);
            }
            ret += max_w;
        }
        return ret >> 1;
    }

private:
    inline int encode(int e) const {
        return e + size + 1; // should be >= 3
    }

    inline weight_t reduced_cost(int u, int v, const Edge& e) const {
        return potential[u] + potential[v] - e.weight;
    }

    inline weight_t reduced_cost(int eid) const {
        return reduced_cost(edges[eid].from, edges[eid].to, edges[eid]);
    }

    void rematch(int v, int w) {
        auto t = mate[v]; mate[v] = w;
        if (mate[t] != v) return;
        if (label[v].to == 0) {
            mate[t] = label[v].from;
            rematch(mate[t], t);
        }
        else {
            int x = label[v].from, y = label[v].to;
            rematch(x, y); rematch(y, x);
        }
    }

    Label search_blossom_edge(int bid) const {
        int b = base[bid], bv = b;
        for (; node[bv].next != b; bv = node[node[bv].next].next);
        return { node[bv].from, node[bv].to };
    }

    void label_blossom(int bid, int m, Label l) {
        label[bid] = { l.from, (l.to == surface[l.to]) ? 0 : l.to };
        if (bid <= N) return;
        int b = base[bid]; label_blossom(b, mate[bid] = m, l);
        l = search_blossom_edge(bid);
        for (int bv = b, bw; node[bv].next != b; bv = node[bw].next) {
            label_blossom(bw = node[bv].next, 0, l);
            label_blossom(node[bw].next, node[bw].from, { node[bv].from, node[bv].to });
        }
    }

    int find_mate(int bid) {
        return bid <= N ? mate[bid] : mate[bid] = find_mate(base[bid]);
    }

    void push_inner_blossom_rec(int bid, bool push = true) {
        tree_label[bid] = (bid <= N) ? INNER : UNUSED;
        if (bid > N) {
            int v = base[bid], u = v;
            do { push_inner_blossom_rec(v, push); } while ((v = node[v].next) != u);
        }
        else if (push) inner_vertices[inner_vertices_size++] = bid;
    }

    void push_inner_blossom(int bid) {
        if (tree_label[bid] != UNUSED) return;
        bool push = label[bid].from != SEPARATED;
        if (bid > N) {
            if (push) inner_blossoms[inner_blossom_size++] = bid;
            push_inner_blossom_rec(bid, push);
        }
        else if (push) inner_vertices[inner_vertices_size++] = bid;
        tree_label[bid] = INNER;
    }

    void push_outer_blossom_rec(int bid) {
        tree_label[bid] = (bid <= N) ? OUTER : UNUSED;
        if (bid > N) {
            int v = base[bid], u = v;
            do { push_outer_blossom_rec(v); } while ((v = node[v].next) != u);
        }
        else outer_vertices.enqueue(bid);
    }

    void push_outer_blossom(int bid, bool push) {
        push_outer_blossom_rec(bid);
        if (bid <= N) return;
        if (push) outer_blossoms[outer_blossom_size++] = bid, tree_label[bid] = OUTER;
        else tree_label[bid] = UNUSED;
    }

    inline void merge_edge(int x, int bx, int eid) {
        auto& e = edges[eid];
        int y = e.to, by = surface[y];
        if (tree_label[by] != OUTER || bx == by) return;
        auto r_cost = reduced_cost(x, y, e);
        if (r_cost < best_cost[by].first) {
            if (best_cost[by].first == INF) merged_edges[merged_edge_size++] = by;
            best_cost[by] = { r_cost, eid };
        }
    }

    inline void merge_vertex(int x, int bx) {
        rep(eid, offsets[x], offsets[x + 1]) merge_edge(x, bx, eid);
        best_edge[x] = UNDEFINED;
    }

    void clear_best_edges(int b) {
        if (b > N) {
            int v = b = base[b];
            do { clear_best_edges(v); } while ((v = node[v].next) != b);
        }
        else best_edge[b] = UNDEFINED;
    }

    void merge_outer(int b, int bid) {
        if (b > N) {
            for (int head = blist_head[b]; head >= 0; head = bnode[head].next) {
                int eid = bnode[head].eid;
                merge_edge(edges[eid].from, bid, eid);
                next_bnode.push_back(head);
            }
            blist_head[b] = -1;
            clear_best_edges(b);
        }
        else merge_vertex(b, bid);
    }

    void merge_inner(int b, int bid) {
        if (b > N) {
            int v = b = base[b];
            do { merge_inner(v, bid); } while ((v = node[v].next) != b);
        }
        else merge_vertex(b, bid);
    }

    void build_linked_list(int bid) {
        if (bid <= N) return;
        int last = -1;
        for (; merged_edge_size > 0; ) {
            int nid = next_bnode.back(); next_bnode.pop_back();
            int by = merged_edges[--merged_edge_size], eid = best_cost[by].second;
            int x = edges[eid].from, y = edges[eid].to;
            bnode[nid] = { eid, last };
            if (tree_label[y] == OUTER) update_best_edge(y, by, best_cost[by].first, eid);
            if (best_edge[x] == UNDEFINED || best_cost[by].first < reduced_cost(best_edge[x])) {
                best_edge[x] = eid;
            }
            best_cost[by] = { INF, UNDEFINED };
            last = nid;
        }
        blist_head[bid] = last;
    }

    void merge_best_edges(int bid, int inner_count) {
        rep(i, 0, inner_count) {
            int bv = outer_blossoms[outer_blossom_size + i];
            if (bv >= 0) merge_outer(bv, bid), merge_inner(node[bv].next, bid);
            else merge_inner(~bv, bid), merge_outer(node[~bv].next, bid);
        }
        merge_outer(base[bid], bid);
        build_linked_list(bid);
    }

    void contract(int x, int y, int eid) {
        int s = surface[x], t = surface[y];
        if (s == t) return;
        auto h = label[surface[mate[s]]].from = label[surface[mate[t]]].from = -encode(eid);

        int lca = -1;
        for (; ; label[surface[mate[s]]].from = h) {
            if (mate[t] != 0) swap(s, t);
            s = lca = surface[label[s].from];
            if (label[surface[mate[s]]].from == h) break;
        }

        int inner_count = 0;
        for (int dir = 0; dir < 2; ++dir) {
            int v = (dir == 0) ? x : y;
            while (1) {
                int bv = surface[v], mv = mate[bv], bmv = surface[mv];
                if (bv == lca) break;
                label[mv] = label[bmv] = { x, y };
                auto n = node[bmv];
                if (!dir) {
                    node[bv] = { bmv, mate[mv], mv };
                    node[bmv].next = surface[n.to];
                }
                else {
                    node[surface[n.to]] = { bmv, n.to, n.from };
                    node[bmv] = { bv, mv, mate[mv] };
                }
                push_outer_blossom(bmv, false);
                v = label[bv].from;

                // Caution: used as temporary array
                outer_blossoms[outer_blossom_size + (inner_count++)] = !dir ? bv : ~bmv;
            }
        }
        node[surface[y]] = { surface[x], y, x };

        int bid = next_bid.back(); next_bid.pop_back();
        base[bid] = lca, label[bid].from = label[lca].from, mate[bid] = mate[lca];

        tree_label[bid] = OUTER;
        set_surface(bid, bid);
        merge_best_edges(bid, inner_count);

        outer_blossoms[outer_blossom_size++] = bid;
    }

    inline void update_best_edge(int y, int by, weight_t r_cost, int eid) {
        if (tree_label[by] != OUTER && best_edge[y] == UNDEFINED) {
            neighbors[neighbor_size++] = y;
        }
        if (best_edge[y] == UNDEFINED || r_cost < reduced_cost(best_edge[y])) {
            best_edge[y] = eid;
        }
    }

    void build_edge_list(int b) {
        if (b <= N) return;
        merge_inner(b, b);
        build_linked_list(b);
    }

    bool augmented(int root, int s) {
        if (s == 0) {
            int br = surface[root];
            push_outer_blossom(br, true);
            label_blossom(br, 0, { 0, 0 });
            build_edge_list(br);
        }
        for (; !outer_vertices.empty() || s > 0; s = 0) {
            auto x = (s > 0) ? s : outer_vertices.dequeue();
            if (potential[x] == 0) {
                if (root != x) rematch(x, 0);
                return true;
            }
            rep(eid, offsets[x], offsets[x + 1]) {
                int bx = surface[x], y = edges[eid].to, by = surface[y];
                if (bx == by) continue;
                auto r_cost = reduced_cost(x, y, edges[eid]);
                if (r_cost > 0 || tree_label[by] != OUTER) {
                    update_best_edge(y, by, r_cost, eid);
                    if (r_cost > 0) continue;
                }
                if (label[by].from >= 0) {
                    contract(x, y, eid);
                    continue;
                }
                if (tree_label[by] == UNUSED) {
                    push_inner_blossom(by);
                    if (by != y) label_blossom(by, find_mate(by), { DEFAULT, 0 });
                }
                int z = mate[by];
                if (z == 0 && by != surface[root]) {
                    rematch(x, y); rematch(y, x);
                    return true;
                }
                int bz = surface[z];
                if (label[bz].from < 0) {
                    node[by] = { -1, y, x };
                    push_outer_blossom(bz, true);
                    label_blossom(bz, mate[z], { x, y });
                    build_edge_list(bz);
                }
            }
        }
        return false;
    }

    void set_surface(int b, int bid) {
        for (int v = base[b]; surface[v] != bid; v = node[v].next) {
            if (v > N) tree_label[v] = UNUSED, set_surface(v, bid);
            surface[v] = bid;
        }
    }

    void reset_surface(int b, int bid) {
        surface[b] = bid;
        if (b <= N) return;
        for (b = base[b]; surface[b] != bid; b = node[b].next) reset_surface(b, bid);
    }

    void separate_blossom(int bid, bool push_blossom = true) {
        tree_label[bid] = UNUSED, label[bid].from = SEPARATED;
        if (bid <= N) return;
        if (push_blossom) inner_blossoms[inner_blossom_size++] = bid;
        for (int b = base[bid]; label[b].from != SEPARATED; b = node[b].next) {
            separate_blossom(b, false);
        }
    }

    void reverse_blossom(int b) {
        int v = b, fr = node[b].from, to = node[b].to;
        for (int nv = node[v].next; nv != b; ) {
            int nnext = node[nv].next, nfr = node[nv].from, nto = node[nv].to;
            node[nv].next = v, node[nv].from = to, node[nv].to = fr;
            fr = nfr, to = nto, v = nv, nv = nnext;
        }
        node[b].next = v, node[b].from = to, node[b].to = fr;
    }

    void expand_blossom(int bid) {
        next_bid.push_back(bid); tree_label[bid] = UNUSED;
        for (int b = base[bid]; surface[b] == bid; b = node[b].next) reset_surface(b, b);
        int old_base = base[bid], target = surface[node[bid].from];
        if (mate[node[target].from] == node[target].to) reverse_blossom(old_base);
        for (int b = target; node[b].next != old_base; ) {
            separate_blossom(b = node[b].next); separate_blossom(b = node[b].next);
        }
        node[target] = node[bid];
        for (int b = old_base; ; b = node[b].next) {
            label[b].from = DEFAULT, tree_label[b] = INNER;
            if (b > N) inner_blossoms[inner_blossom_size++] = b;
            int m = find_mate(b), bm = surface[m];
            if (b != old_base) mate[bm] = mate[m];
            label[m] = label[bm] = { node[b].to, node[b].from };
            if (b == target) break;
            push_outer_blossom(b = node[b].next, true);
            build_edge_list(b);
        }
        base[bid] = bid, surface[bid] = bid;
    }

    void update_potential(int* vs, int s, weight_t delta, int label) {
        rep(i, 0, s) {
            int x = vs[i];
            if (tree_label[x] != label) continue;
            potential[x] += delta;
        }
    }

    int adjust_dual_solutions() {
        pair<weight_t, int> delta1(INF, 0), delta2(INF, 0), delta3(INF, 0), delta4(INF, 0);
        rep(i, 0, outer_vertices.size()) {
            int y = outer_vertices[i], eid = best_edge[y];
            delta1 = min(delta1, { potential[y], y });
            if (eid != UNDEFINED) {
                delta3 = min(delta3, { reduced_cost(eid) >> 1, y });
            }
        }
        rep(i, 0, neighbor_size) {
            int y = neighbors[i];
            if (tree_label[y] == UNUSED) {
                int eid = best_edge[y], x = edges[eid].from;
                delta2 = min(delta2, { reduced_cost(x, y, edges[eid]), x });
            }
        }
        rep(i, 0, inner_blossom_size) if (tree_label[inner_blossoms[i]] == INNER) {
            int b = inner_blossoms[i];
            delta4 = min(delta4, { potential[b] >> 1, b });
        }
        auto delta = min(min(delta1, delta2), min(delta3, delta4));
        auto d = delta.first;
        update_potential(outer_vertices.data(), outer_vertices.size(), -1 * d, OUTER);
        update_potential(inner_vertices.data(), inner_vertices_size, 1 * d, INNER);
        update_potential(outer_blossoms.data(), outer_blossom_size, 2 * d, OUTER);
        update_potential(inner_blossoms.data(), inner_blossom_size, -2 * d, INNER);
        if (delta4.first == d) {
            expand_blossom(delta4.second);
            return -1;
        }
        else {
            return delta.second;
        }
    }

    void fix_blossom_bases() {
        int remain = size - next_bid.size() - (N + 1);
        for (int bid = N + 1; bid < size && remain > 0; ++bid) if (base[bid] != bid) {
            int b = base[bid];
            for (int skipped = 0; skipped < 2;) {
                b = node[b].next;
                if (mate[node[b].from] == node[b].to) skipped = 0;
                else skipped++;
            }
            base[bid] = b;
            --remain;
        }
    }

    void free_edge_list(int x) {
        for (int head = blist_head[x]; head >= 0; head = bnode[head].next) {
            next_bnode.push_back(head);
        }
        blist_head[x] = -1;
    }

    void clear_vertices(int* vs, int size) {
        rep(i, 0, size) {
            int v = vs[i];
            label[v] = { DEFAULT, 0 }; tree_label[v] = UNUSED; best_edge[v] = UNDEFINED;
        }
    }

    void clear_label() {
        label[0] = { DEFAULT, 0 };
        clear_vertices(outer_vertices.data(), outer_vertices.size()); outer_vertices.clear();
        clear_vertices(inner_vertices.data(), inner_vertices_size); inner_vertices_size = 0;
        clear_vertices(outer_blossoms.data(), outer_blossom_size);
        rep(i, 0, outer_blossom_size) if (blist_head[outer_blossoms[i]] >= 0) free_edge_list(outer_blossoms[i]);
        outer_blossom_size = 0;
        clear_vertices(inner_blossoms.data(), inner_blossom_size); inner_blossom_size = 0;
        rep(i, 0, neighbor_size) best_edge[neighbors[i]] = UNDEFINED;
        neighbor_size = 0;
    }

    void set_potential() {
        potential.resize(size);
        rep(u, 1, N + 1) {
            weight_t max_w = 0;
            rep(eid, offsets[u], offsets[u + 1]) max_w = max(max_w, edges[eid].weight);
            potential[u] = max_w >> 1;
        }
    }

    void initialize() {
        mate.assign(size, 0);
        label.assign(size, { -1, 0 });

        surface.resize(size); rep(i, 0, size) surface[i] = i;
        base.resize(size); rep(i, 0, size) base[i] = i;
        node.resize(size); rep(i, 0, size) node[i] = { i, i, i };

        outer_vertices = Queue(N);
        inner_vertices.resize(N + 1); inner_vertices_size = 0;
        outer_blossoms.resize(B); outer_blossom_size = 0;
        inner_blossoms.resize(B); inner_blossom_size = 0;

        tree_label.assign(size, UNUSED);

        next_bid.resize(B);
        rep(i, 0, B) next_bid[i] = size - 1 - i;

        merged_edges.resize(N + 1); merged_edge_size = 0;
        best_cost.assign(size, { INF, UNDEFINED });

        neighbors.resize(N + 1); neighbor_size = 0;
        best_edge.assign(size, UNDEFINED);

        blist_head.assign(size, -1);
        next_bnode.resize(edges.size());
        rep(i, 0, edges.size()) next_bnode[i] = edges.size() - 1 - i;

        bnode.resize(edges.size());
    }

private:
    int N, B, size;
    vector<Edge> edges;
    vector<int> offsets;

    vector<Label> label;
    vector<int> mate, surface, base;
    vector<Node> node;
    vector<weight_t> potential;

    vector<int> next_bid;

    vector<i8> tree_label;

    Queue outer_vertices;
    vector<int> inner_vertices; int inner_vertices_size;
    vector<int> outer_blossoms; int outer_blossom_size;
    vector<int> inner_blossoms; int inner_blossom_size;

    vector<int> merged_edges; int merged_edge_size;
    vector< pair<weight_t, int> > best_cost;
    vector<int> neighbors; int neighbor_size;
    vector<int> best_edge;

    vector<int> blist_head;
    vector<LinkedList> bnode;
    vector<int> next_bnode;
};

/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/


typedef MaximumWeightedMatching<int> MWM;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    
    vector<MWM::Edge> e;
    rep(a, 0, N) rep(b, 0, N) {
        int c; cin >> c;
        if (a < b && 0 <= c) e.push_back(MWM::Edge(a + 1, b + 1, c));
    }

    MWM m(N, e);
    int ans = m.maximum_weighted_matching();
    cout << ans << endl;
}
yukicoder

結果

テストケース

ソースコード
