vertex_cut

[Astral-23]

頂点s -> tのパスをなくすために消すべき頂点の最小個数or 頂点ごとにコストがある時、コストのｍin

template <typename Cost, bool directed> struct vertex_cut {
    const Cost inf = numeric_limits<Cost>::max() / 4;
    int n;
    atcoder::mf_graph<Cost> gh;
    vertex_cut(int n) : vertex_cut(vector<Cost>(n, 1)) {}
    vertex_cut(const vector<Cost> &C) : n(C.size()), gh(2*n) {
        for (int i = 0; i < n; i++) {
            gh.add_edge(i, i + n, C[i]);
        }
    }

    void add_edge(int s, int t) {
        gh.add_edge(s + n, t, inf);
        if (directed == false) {
            gh.add_edge(t + n, s, inf);
        }
    }

    Cost run(int s, int t) {
        Cost fl = gh.flow(s, t);
        return fl;
    }
};

$O(n^2m)$ https://atcoder.jp/contests/arc074/submissions/58765904

[Astral-23]

v事に v_inとv_outを作る。 vを消す ⇔ v_in -> v_out の辺を消す　となる v_in -> v_out のコストを削除のコストにすれば良い 同様に、辺だけ消すことを許容するときは、辺のコストをinfじゃなくする