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

• 問題: No.519 アイドルユニット
• ユーザー: はまやんはまやん
• 提出日時: 2017-08-08 10:24:24
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 20,446 bytes
• コンパイル時間: 4,092 ms
• コンパイル使用メモリ: 221,236 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-12 00:09:11
• 合計ジャッジ時間: 5,255 ms
• ジャッジサーバーID （参考情報）: judge3 / 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	1 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	2 ms; 5,248 KB
testcase_25	AC	2 ms; 5,248 KB
testcase_26	AC	2 ms; 5,248 KB
testcase_27	AC	1 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	1 ms; 5,248 KB

コンパイルメッセージ

main.cpp: In member function 'void MaxWeightMatching::mainLoop()':
main.cpp:460:34: warning: 'deltaBlossom' may be used uninitialized [-Wmaybe-uninitialized]
  460 |                     expandBlossom(deltaBlossom, false);
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:385:32: note: 'deltaBlossom' was declared here
  385 |                 int deltaEdge, deltaBlossom;
      |                                ^~~~~~~~~~~~
main.cpp:446:40: warning: 'deltaEdge' may be used uninitialized [-Wmaybe-uninitialized]
  446 |                     allowEdge[deltaEdge] = true;
      |                                        ^
main.cpp:385:21: note: 'deltaEdge' was declared here
  385 |                 int deltaEdge, deltaBlossom;
      |                     ^~~~~~~~~
main.cpp:393:50: warning: 'delta' may be used uninitialized [-Wmaybe-uninitialized]
  393 |                         if (deltaType == -1 || d < delta) {
      |                                                ~~^~~~~~~
main.cpp:384:24: note: 'delta' was declared here
  384 |                 Weight delta;
      |                        ^~~~~

ソースコード

#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(); }
//---------------------------------------------------------------------------------------------------
typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src_, int dst_, Weight weight_) : src(src_), dst(dst_), weight(weight_) { }
    Edge() {};
};
typedef vector<Edge> Edges;
typedef vector<int> vi;
struct MaxWeightMatching {
    int nEdge, nVertex;
    Weight maxWeight;
    vi endPoint, mate, label, labelEdge,
        inBlossom, blossomParent, blossomBase,
        bestEdge, unusedBlossoms, allowEdge,
        blossomBestEdgesUsed,
        sVerteices;
    vector<Weight> dualVar;
    vector<vi> neighbEnd, blossomChilds, blossomEdges,
        blossomBestEdges;
    Edges edges;
    bool maxCardinality;

    Weight slack(int k) {
        Edge &e = edges[k];
        return dualVar[e.src] + dualVar[e.dst] - 2 * e.weight;
    }
    struct BlossomLeaves {
        int b;
        MaxWeightMatching *mw;
        enum { INITAL, END, NEXT, THIRD } state;
        vi::const_iterator iter, endi;
        BlossomLeaves *bl;
        BlossomLeaves(MaxWeightMatching *mw_, int b_) :
            mw(mw_), b(b_), state(INITAL), bl(NULL) {}
        bool next(int &r) {
            int t;
            switch (state) {
            case INITAL:
                if (b < mw->nVertex) {
                    r = b;
                    state = END;
                    return true;
                }
                else {
                    iter = mw->blossomChilds[b].begin();
                    endi = mw->blossomChilds[b].end();
                    state = NEXT;
                    return next(r);
                }
            case END:
                return false;
            case NEXT:
                if (iter == endi)
                    return false;
                t = *iter;
                ++iter;
                if (t < mw->nVertex) {
                    r = t;
                    return true;
                }
                else {
                    bl = new BlossomLeaves(mw, t);
                    state = THIRD;
                    return next(r);
                }
            case THIRD:
                if (!bl->next(t)) {
                    state = NEXT;
                    delete bl; bl = NULL;
                    return next(r);
                }
                else {
                    r = t;
                    return true;
                }
            }
            return false;
        }
    };
    void assignLabel(int w, int t, int p) {
        int b = inBlossom[w];
        label[w] = label[b] = t;
        labelEdge[w] = labelEdge[b] = p;
        bestEdge[w] = bestEdge[b] = -1;
        if (t == 1) {
            BlossomLeaves bl(this, b);
            for (int r; bl.next(r); ) sVerteices.push_back(r);
        }
        else if (t == 2) {
            int base = blossomBase[b];
            assignLabel(endPoint[mate[base]], 1, mate[base] ^ 1);
        }
    }
    int scanBlossom(int v, int w) {
        vi path;
        int base = -1;
        while (v != -1) {
            int b = inBlossom[v];
            if (label[b] & 4) {
                base = blossomBase[b];
                break;
            }
            path.push_back(b);
            label[b] = 5;
            if (labelEdge[b] == -1) {
                v = -1;
            }
            else {
                v = endPoint[labelEdge[b]];
                b = inBlossom[v];
                v = endPoint[labelEdge[b]];
            }
            if (w != -1)
                swap(v, w);
        }
        fore(it, path) label[it] = 1;
        return base;
    }
    void addBlossom(int base, int k) {
        Edge &e = edges[k];
        int bb = inBlossom[base],
            bv = inBlossom[e.src],
            bw = inBlossom[e.dst];
        int b = unusedBlossoms.back(); unusedBlossoms.pop_back();
        blossomBase[b] = base;
        blossomParent[b] = -1;
        blossomParent[bb] = b;
        blossomChilds[b].clear();
        blossomEdges[b].clear();
        vi &bChilds = blossomChilds[b];
        vi &bEdges = blossomEdges[b];
        while (bv != bb) {
            blossomParent[bv] = b;
            bChilds.push_back(bv);
            bEdges.push_back(labelEdge[bv]);
            bv = inBlossom[endPoint[labelEdge[bv]]];
        }
        bChilds.push_back(bb);
        reverse(bChilds.begin(), bChilds.end());
        reverse(bEdges.begin(), bEdges.end());
        bEdges.push_back(2 * k);
        while (bw != bb) {
            blossomParent[bw] = b;
            bChilds.push_back(bw);
            bEdges.push_back(labelEdge[bw] ^ 1);
            bw = inBlossom[endPoint[labelEdge[bw]]];
        }
        label[b] = 1;
        labelEdge[b] = labelEdge[bb];
        dualVar[b] = 0;
        BlossomLeaves bl(this, b);
        for (int v; bl.next(v); ) {
            if (label[inBlossom[v]] == 2)
                sVerteices.push_back(v);
            inBlossom[v] = b;
        }
        vi bestEdgeTo(2 * nVertex, -1);
        fore(it, bChilds) {
            int bv2 = it;
            vector<vi> nbLists;
            if (!blossomBestEdgesUsed[bv2]) {
                BlossomLeaves bl2(this, bv2);
                for (int v2; bl2.next(v2); ) {
                    nbLists.push_back(neighbEnd[v2]);
                    vi &vv = nbLists.back();
                    fore(i, vv) i /= 2;
                }
            }
            else {
                nbLists.push_back(blossomBestEdges[bv2]);
            }
            fore(itt, nbLists) {
                fore(ittt, itt) {
                    int k2 = ittt;
                    Edge &e2 = edges[k2];
                    int i = e2.src, j = e2.dst;
                    if (inBlossom[j] == b)
                        swap(i, j);
                    int bj = inBlossom[j];
                    if (bj != b && label[bj] == 1 &&
                        (bestEdgeTo[bj] == -1 ||
                            slack(k2) < slack(bestEdgeTo[bj]))) {
                        bestEdgeTo[bj] = k2;
                    }
                }
            }
            blossomBestEdgesUsed[bv2] = false;
            blossomBestEdges[bv2].clear();
            bestEdge[bv2] = -1;
        }
        blossomBestEdgesUsed[b] = true;
        blossomBestEdges[b].clear();
        fore(it, bestEdgeTo) if (it != -1) blossomBestEdges[b].push_back(it);
        bestEdge[b] = -1;
        fore(it, blossomBestEdges[b])
            if (bestEdge[b] == -1 || slack(it) < slack(bestEdge[b]))
                bestEdge[b] = it;
    }
    void expandBlossom(int b, bool endStage) {
        int cSize = blossomChilds[b].size();
        fore(it, blossomChilds[b]) {
            int s = it;
            blossomParent[s] = -1;
            if (s < nVertex)
                inBlossom[s] = s;
            else if (endStage && dualVar[s] == 0)
                expandBlossom(s, endStage);
            else {
                BlossomLeaves bl(this, s);
                for (int v; bl.next(v); )
                    inBlossom[v] = s;
            }
        }
        if (!endStage && label[b] == 2) {
            int entryChild = inBlossom[endPoint[labelEdge[b] ^ 1]];
            int j = find(blossomChilds[b].begin(), blossomChilds[b].end(), entryChild) - blossomChilds[b].begin();
            int jStep, evenOdd;
            if (j & 1)
                jStep = 1, evenOdd = 0;
            else
                jStep = -1, evenOdd = 1;
            int p = labelEdge[b];
            while (j != 0) {
                label[endPoint[p ^ 1]] = 0;
                label[endPoint[blossomEdges[b][j - evenOdd] ^ evenOdd ^ 1]] = 0;
                assignLabel(endPoint[p ^ 1], 2, p);
                allowEdge[blossomEdges[b][j - evenOdd] / 2] = true;
                j = (j + jStep + cSize) % cSize;
                p = blossomEdges[b][j - evenOdd] ^ evenOdd;
                allowEdge[p / 2] = true;
                j = (j + jStep + cSize) % cSize;
            }
            int bv = blossomChilds[b][j];
            label[endPoint[p ^ 1]] = label[bv] = 2;
            labelEdge[endPoint[p ^ 1]] = labelEdge[bv] = p;
            bestEdge[bv] = -1;
            j = (j + jStep + cSize) % cSize;
            while (blossomChilds[b][j] != entryChild) {
                bv = blossomChilds[b][j];
                if (label[bv] == 1) {
                    j = (j + jStep + cSize) % cSize;
                    continue;
                }
                BlossomLeaves bl(this, bv);
                int v;
                while (bl.next(v))
                    if (label[v] != 0)
                        break;
                if (label[v] != 0) {
                    label[v] = 0;
                    label[endPoint[mate[blossomBase[bv]]]] = 0;
                    assignLabel(v, 2, labelEdge[v]);
                }
                j = (j + jStep + cSize) % cSize;
            }
        }
        label[b] = labelEdge[b] = -1;
        blossomChilds[b].clear();
        blossomEdges[b].clear();
        blossomBestEdgesUsed[b] = false;
        blossomBestEdges[b].clear();
        bestEdge[b] = -1;
        unusedBlossoms.push_back(b);
    }
    void augmentBlossom(int b, int v) {
        int cSize = blossomChilds[b].size();
        int t = v;
        while (blossomParent[t] != b)
            t = blossomParent[t];
        if (t >= nVertex)
            augmentBlossom(t, v);
        int i, j, jStep, evenOdd;
        i = j = find(blossomChilds[b].begin(), blossomChilds[b].end(), t) - blossomChilds[b].begin();
        if (i & 1)
            jStep = 1, evenOdd = 0;
        else
            jStep = -1, evenOdd = 1;
        while (j != 0) {
            j = (j + jStep + cSize) % cSize;
            t = blossomChilds[b][j];
            int p = blossomEdges[b][j - evenOdd] ^ evenOdd;
            if (t >= nVertex)
                augmentBlossom(t, endPoint[p]);
            j = (j + jStep + cSize) % cSize;
            t = blossomChilds[b][j];
            if (t >= nVertex)
                augmentBlossom(t, endPoint[p ^ 1]);
            mate[endPoint[p]] = p ^ 1;
            mate[endPoint[p ^ 1]] = p;
        }
        rotate(blossomChilds[b].begin(), blossomChilds[b].begin() + i, blossomChilds[b].end());
        rotate(blossomEdges[b].begin(), blossomEdges[b].begin() + i, blossomEdges[b].end());
        blossomBase[b] = blossomBase[blossomChilds[b][0]];
    }
    void augmentMatching(int k) {
        Edge &e = edges[k];
        int v = e.src, w = e.dst;
        rep(ii, 0, 2) {
            int s = ii == 0 ? v : w, p = ii == 0 ? 2 * k + 1 : 2 * k;
            while (true) {
                int bs = inBlossom[s];
                if (bs >= nVertex)
                    augmentBlossom(bs, s);
                mate[s] = p;
                if (labelEdge[bs] == -1)
                    break;
                int bt = inBlossom[endPoint[labelEdge[bs]]];
                s = endPoint[labelEdge[bt]];
                int j = endPoint[labelEdge[bt] ^ 1];
                if (bt >= nVertex)
                    augmentBlossom(bt, j);
                mate[j] = labelEdge[bt];
                p = labelEdge[bt] ^ 1;
            }
        }
    }
    void mainLoop() {
        rep(t, 0, nVertex) {
            label.assign(2 * nVertex, 0);
            bestEdge.assign(2 * nVertex, -1);
            fill(blossomBestEdgesUsed.begin() + nVertex, blossomBestEdgesUsed.end(), false);
            allowEdge.assign(nEdge, false);
            sVerteices.clear();
            rep(v, 0, nVertex)
                if (mate[v] == -1 && label[inBlossom[v]] == 0)
                    assignLabel(v, 1, -1);
            bool augmented = false;
            while (true) {
                Weight kSlack;
                while (!sVerteices.empty() && !augmented) {
                    int v = sVerteices.back(); sVerteices.pop_back();
                    fore(it, neighbEnd[v]) {
                        int p = it;
                        int k = p / 2, w = endPoint[p];
                        if (inBlossom[v] == inBlossom[w])
                            continue;
                        if (!allowEdge[k]) {
                            kSlack = slack(k);
                            if (kSlack <= 0)
                                allowEdge[k] = true;
                        }
                        if (allowEdge[k]) {
                            if (label[inBlossom[w]] == 0) {
                                assignLabel(w, 2, p ^ 1);
                            }
                            else if (label[inBlossom[w]] == 1) {
                                int base = scanBlossom(v, w);
                                if (base >= 0) {
                                    addBlossom(base, k);
                                }
                                else {
                                    augmentMatching(k);
                                    augmented = true;
                                    break;
                                }
                            }
                            else if (label[w] == 0) {
                                label[w] = 2;
                                labelEdge[w] = p ^ 1;
                            }
                        }
                        else if (label[inBlossom[w]] == 1) {
                            int b = inBlossom[v];
                            if (bestEdge[b] == -1 || kSlack < slack(bestEdge[b]))
                                bestEdge[b] = k;
                        }
                        else if (label[w] == 0) {
                            if (bestEdge[w] == -1 || kSlack < slack(bestEdge[w]))
                                bestEdge[w] = k;
                        }
                    }
                }
                if (augmented)
                    break;
                int deltaType = -1;
                Weight delta;
                int deltaEdge, deltaBlossom;
                if (!maxCardinality) {
                    deltaType = 1;
                    delta = *min_element(dualVar.begin(), dualVar.begin() + nVertex);
                }
                rep(v, 0, nVertex) {
                    if (label[inBlossom[v]] == 0 && bestEdge[v] != -1) {
                        Weight d = slack(bestEdge[v]);
                        if (deltaType == -1 || d < delta) {
                            delta = d;
                            deltaType = 2;
                            deltaEdge = bestEdge[v];
                        }
                    }
                }
                rep(b, 0, 2 * nVertex) {
                    if (blossomParent[b] == -1 && label[b] == 1 && bestEdge[b] != -1) {
                        kSlack = slack(bestEdge[b]);
                        Weight d = kSlack / 2;
                        if (deltaType == -1 || d < delta) {
                            delta = d;
                            deltaType = 3;
                            deltaEdge = bestEdge[b];
                        }
                    }
                }
                rep(b, nVertex, 2 * nVertex) {
                    if (blossomBase[b] >= 0 && blossomParent[b] == -1 &&
                        label[b] == 2 &&
                        (deltaType == -1 || dualVar[b] < delta)) {
                        delta = dualVar[b];
                        deltaType = 4;
                        deltaBlossom = b;
                    }
                }
                if (deltaType == -1) {
                    deltaType = 1;
                    delta = max((Weight)0, *min_element(dualVar.begin(), dualVar.begin() + nVertex));
                }
                rep(v, 0, nVertex) {
                    if (label[inBlossom[v]] == 1) {
                        dualVar[v] -= delta;
                    }
                    else if (label[inBlossom[v]] == 2) {
                        dualVar[v] += delta;
                    }
                }
                rep(b, nVertex, 2 * nVertex) {
                    if (blossomBase[b] >= 0 && blossomParent[b] == -1) {
                        if (label[b] == 1) {
                            dualVar[b] += delta;
                        }
                        else if (label[b] == 2) {
                            dualVar[b] -= delta;
                        }
                    }
                }
                if (deltaType == 1) {
                    break;
                }
                else if (deltaType == 2) {
                    allowEdge[deltaEdge] = true;
                    Edge &e = edges[deltaEdge];
                    int i = e.src, j = e.dst;
                    if (label[inBlossom[i]] == 0)
                        swap(i, j);
                    sVerteices.push_back(i);
                }
                else if (deltaType == 3) {
                    allowEdge[deltaEdge] = true;
                    Edge &e = edges[deltaEdge];
                    int i = e.src;
                    sVerteices.push_back(i);
                }
                else if (deltaType == 4) {
                    expandBlossom(deltaBlossom, false);
                }
            }
            if (!augmented)
                break;
            rep(b, nVertex, 2 * nVertex)
                if (blossomParent[b] == -1 && blossomBase[b] >= 0 &&
                    label[b] == 1 && dualVar[b] == 0)
                    expandBlossom(b, true);
        }
    }
    vi matching(const Edges& edges_, bool maxCardinality_ = false) {
        edges = edges_; maxCardinality = maxCardinality_;
        nEdge = edges.size();
        nVertex = 0;
        fore(i, edges) {
            if (i.src >= nVertex) nVertex = i.src + 1;
            if (i.dst >= nVertex) nVertex = i.dst + 1;
        }
        maxWeight = 0;
        endPoint.clear();
        neighbEnd.assign(nVertex, vi());
        rep(i, 0, nEdge) {
            Edge &e = edges[i];
            maxWeight = max(maxWeight, e.weight);
            endPoint.push_back(e.src);
            endPoint.push_back(e.dst);
            neighbEnd[e.src].push_back(2 * i + 1);
            neighbEnd[e.dst].push_back(2 * i);
        }
        mate.assign(nVertex, -1);
        label.assign(2 * nVertex, 0);
        labelEdge.assign(2 * nVertex, -1);
        inBlossom.clear();
        blossomBase.clear();
        blossomParent.assign(2 * nVertex, -1);
        blossomChilds.assign(2 * nVertex, vi());
        blossomEdges.assign(2 * nVertex, vi());
        bestEdge.assign(2 * nVertex, -1);
        blossomBestEdgesUsed.assign(2 * nVertex, false);
        blossomBestEdges.assign(2 * nVertex, vi());
        unusedBlossoms.clear();
        dualVar.clear();
        rep(i, 0, nVertex)
            inBlossom.push_back(i),
            blossomBase.push_back(i),
            unusedBlossoms.push_back(nVertex + i),
            dualVar.push_back(maxWeight);
        rep(i, 0, nVertex)
            blossomBase.push_back(-1),
            dualVar.push_back(0);
        allowEdge.assign(nEdge, 0);
        sVerteices = vi();
        mainLoop();
        rep(v, 0, nVertex)
            if (mate[v] >= 0)
                mate[v] = endPoint[mate[v]];
        return mate;
    }
    Weight getWeight(const Edges& e, bool maxCardinality_ = false) {
        vector<int> v = matching(e, maxCardinality_);
        Weight w = 0;
        rep(i, 0, v.size()) if (v[i] != -1)
            fore(j, e) if (i == j.src && j.dst == v[i]) w += j.weight;
        return w;
    }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    Edges e;
    rep(a, 0, N) rep(b, 0, N) {
        int c; cin >> c;
        if (a < b && 0 <= c) e.push_back(Edge(a, b, c));
    }

    MaxWeightMatching m;
    int ans = m.getWeight(e);
    cout << ans << endl;
}