提出 #73407755

---

ソースコード 拡げる

//utf-8

#include <vector>
#include <cstdint>
#include <string>
#include <algorithm>
#include <limits>
#include <iterator>
#include <utility>

#include <cassert>
#include <iostream>

#include <exception>

#define bound_flow_less_edge

namespace flow_algo {

    using size_t = std::uint32_t;
    using flow_t = std::uint64_t;
    using cost_t = std::int64_t;
    using std::vector;
    using std::basic_string;
    using std::forward;
    using signed_flow_t = std::int64_t;
    using std::pair;
    using std::make_pair;
    using std::swap;
    using std::runtime_error;

    constexpr flow_t flow_max_v = std::numeric_limits<flow_t>::max();

    struct edge {
        size_t to;
        flow_t flow;
        edge(size_t t = -1, flow_t fl = 1) : to(t), flow(fl) {}
        bool empty() const { return to == (size_t)-1; }
    };

    struct network {
        vector<edge> edges;
        vector<vector<size_t> > vertexs;
        size_t source, sink;// 源汇
        network() : edges{}, vertexs{}, source{}, sink{} {}
        void set_vertex(size_t n, size_t S, size_t T){
            edges.clear();
            vertexs.clear();
            vertexs.resize(n);
            source = S, sink = T;
        }
        void clear(){
            set_vertex(0, 0, 0);
        }
        typedef size_t edge_handle;
        edge_handle add_edge(size_t from, size_t to, flow_t flow = 1){
            size_t ret = edges.size();
            edges.emplace_back(to, flow);
            edges.emplace_back(from, 0);
            vertexs[from].emplace_back(ret);
            vertexs[to].emplace_back(++ret);
            return (edges.size() - 2) >> 1;
        }
        void reset(edge_handle idx){
            edges[idx << 1].flow += edges[idx << 1 | 1].flow;
            edges[idx << 1 | 1].flow = 0;
        }
        void clear(edge_handle idx){
            edges[idx << 1].flow = edges[idx << 1 | 1].flow = 0;
        }
        void grow_flow(edge_handle idx, flow_t fl){
            edges[idx << 1].flow += fl;
        }
        flow_t flow_of(edge_handle idx) const {
            return edges[idx << 1 | 1].flow;
        }
        flow_t capacity_of(edge_handle idx) const {
            return edges[idx << 1].flow + edges[idx << 1 | 1].flow;
        }
        void reset_flow(){
            for (size_t i = 0, _ = edges.size(); i != _; i += 2)
                edges[i].flow += edges[i ^ 1].flow, edges[i ^ 1].flow = 0;
        }

        flow_t EK_max_flow(){// EK 算法
            size_t n = vertexs.size();
            vector<size_t> pre(n);
            vector<flow_t> dis(n);
            auto bfs = [&]{
                std::fill_n(dis.begin(), n, 0);
                basic_string<bool> vis; vis.resize(n);
                std::fill_n(pre.begin(), n, 0);
                vector<size_t> queue(n);
                vector<size_t>::iterator head = queue.begin(), tail = std::next(head);
                vis[*head = source] = true;
                dis[source] = flow_max_v;
                while (head != tail){
                    size_t u = *head; ++head;
                    for (size_t id : vertexs[u]){
                        size_t to = edges[id].to;
                        flow_t fl = edges[id].flow;
                        if (fl && !vis[to]){
                            dis[to] = std::min(dis[u], fl);
                            vis[to] = true, pre[to] = id, *tail = to, ++tail;
                        }
                    }
                }
                return (bool)dis[sink];
            };
            flow_t ret = 0;
            while (bfs()){
                ret += dis[sink];
                for (size_t u = sink; u != source; u = edges[pre[u] ^ 1].to)
                    edges[pre[u]].flow -= dis[sink], edges[pre[u] ^ 1].flow += dis[sink];
            }
            return ret;
        }

        flow_t DINIC_max_flow(flow_t max_flow = flow_max_v){// Dinic 算法
            if (!max_flow)return 0;
            typedef vector<size_t>::iterator iter_t;
            size_t n = vertexs.size();
            vector<size_t> d(n);
            vector<size_t> now(n);// 当前弧优化
            auto bfs = [&]{
                std::fill_n(d.begin(), n, 0);
                std::fill_n(now.begin(), n, 0);
                vector<size_t> queue(n);
                iter_t head = queue.begin(), tail = std::next(head);
                *head = source;
                d[source] = 1;
                while (head != tail){
                    size_t u = *head; ++head;
                    for (size_t id : vertexs[u]){
                        size_t to = edges[id].to;
                        flow_t fl = edges[id].flow;
                        if (fl && !d[to])d[to] = d[u] + 1, *tail = to, ++tail;
                    }
                }
                return (bool)d[sink];
            };
            auto dfs = [&](size_t u, flow_t sm){
                auto dfs_ = [&](auto &&self, size_t u, flow_t sm) -> flow_t {
                    if (u == sink)return sm;
                    flow_t ret = 0;
                    for (iter_t it = vertexs[u].begin() + now[u], end = vertexs[u].end(); it != end; ++it, ++now[u]){
                        size_t to = edges[*it].to;
                        flow_t &fl = edges[*it].flow;
                        if (fl && d[to] == d[u] + 1){
                            flow_t nx = self(self, to, std::min(sm, fl));
                            if (!nx)d[to] = -1;
                            else {
                                fl -= nx, sm -= nx, ret += nx;
                                edges[*it ^ 1].flow += nx;
                                if (!sm)return ret;
                            }
                        }
                    }
                    return ret;
                };
                return dfs_(dfs_, u, sm);
            };
            flow_t ret = 0;
            while (bfs() && ret < max_flow)ret += dfs(source, max_flow - ret);
            return ret;
        }

        vector<size_t> min_cut() const {// 返回 S 集合中的点，在残量网络上求
            typedef vector<size_t>::iterator iter_t;
            size_t n = vertexs.size();
            basic_string<bool> vs; vs.resize(n);
            vector<size_t> ret;
            vector<size_t> queue(n);
            iter_t head = queue.begin(), tail = std::next(head);
            *head = source;
            vs[source] = true;
            ret.emplace_back(source);
            while (head != tail){
                size_t u = *head; ++head;
                for (size_t id : vertexs[u]){
                    size_t to = edges[id].to;
                    if (edges[id].flow && !vs[to]){
                        vs[to] = true;
                        ret.emplace_back(to);
                        *tail = to;
                        ++tail;
                    }
                }
            }
            return ret;
        }

        bool reach(size_t from, size_t to){
            typedef vector<size_t>::iterator iter_t;
            size_t n = vertexs.size();
            vector<size_t> queue(n);
            basic_string<bool> d;d.resize(n);
            iter_t head = queue.begin(), tail = std::next(head);
            *head = from;
            while (head != tail){
                size_t u = *head; ++head;
                for (size_t id : vertexs[u]){
                    size_t t = edges[id].to;
                    flow_t fl = edges[id].flow;
                    if (fl && !d[t]){
                        if (t == to)return true;
                        d[t] = d[u] + 1, *tail = t, ++tail;
                    }
                }
            }
            return false;
        }

        typedef flow_t flow_result_t;

        flow_t flow(size_t _S, size_t _T, flow_t max_flow = flow_max_v){
            if (!max_flow)return 0;
            swap(source, _S), swap(sink, _T);
            flow_t ret = DINIC_max_flow(max_flow);
            swap(source, _S), swap(sink, _T);
            return ret;
        }

        flow_t remove(edge_handle id){ // 删除边并退流，返回退的流量，保证删除之后网络合法，但不保证删除后的网络无增广路
            size_t from = edges[id << 1 | 1].to, to = edges[id << 1].to;
            flow_t flw = edges[id << 1 | 1].flow;
            flow(sink, to, flw);
            flow(from, source, flw);
            edges[id << 1].flow = edges[id << 1 | 1].flow = 0;
            return flw;
        }

    };

    struct edge_with_cost {
        size_t to;
        flow_t flow;
        cost_t cost;
        edge_with_cost(size_t t = -1, flow_t fl = 1, cost_t cs = 1) : to(t), flow(fl), cost(cs) {}
        bool empty() const { return to == (size_t)-1; }
    };

    struct cost_and_flow {
        cost_t cost;
        flow_t flow;
        cost_and_flow(cost_t cs, flow_t fl) : cost(cs), flow(fl) {}
    };

    struct network_with_cost {
        vector<edge_with_cost> edges;
        vector<vector<size_t> > vertexs;
        size_t source, sink;
        network_with_cost() : edges{}, vertexs{}, source{}, sink{} {}
        void set_vertex(size_t n, size_t S, size_t T){
            edges.clear();
            vertexs.clear();
            vertexs.resize(n);
            source = S, sink = T;
        }
        typedef size_t edge_handle;
        edge_handle add_edge(size_t from, size_t to, flow_t fl, cost_t cs){
            size_t ret = edges.size();
            edges.emplace_back(to, fl, cs);
            edges.emplace_back(from, 0, -cs);
            vertexs[from].emplace_back(ret);
            vertexs[to].emplace_back(++ret);
            return (edges.size() - 2) >> 1;
        }
        void reset(edge_handle idx){
            edges[idx << 1].flow += edges[idx << 1 | 1].flow;
            edges[idx << 1 | 1].flow = 0;
        }
        void clear(edge_handle idx){
            edges[idx << 1].flow = edges[idx << 1 | 1].flow = 0;
        }
        flow_t flow_of(edge_handle idx) const {
            return edges[idx << 1 | 1].flow;
        }
        flow_t capacity_of(edge_handle idx) const {
            return edges[idx << 1].flow + edges[idx << 1 | 1].flow;
        }
        void grow_flow(edge_handle idx, flow_t fl){
            edges[idx << 1].flow += fl;
        }
        void set_cost(edge_handle idx, cost_t cs){
            edges[idx << 1].cost = cs;
            edges[idx << 1 | 1].cost = -cs;
        }
        void reset_flow(){
            for (size_t i = 0, _ = edges.size(); i != _; i += 2)
                edges[i].flow += edges[i ^ 1].flow, edges[i ^ 1].flow = 0;
        }

        cost_and_flow EK_min_cost(bool flow_max = true){
            size_t n = vertexs.size();
            vector<size_t> pre(n);
            vector<flow_t> dis(n);
            vector<cost_t> dcs(n);
            auto spfa = [&]{
                std::fill_n(dis.begin(), n, 0);
                basic_string<bool> inq; inq.resize(n);
                std::fill_n(pre.begin(), n, 0);
                std::fill_n(dcs.begin(), n, std::numeric_limits<cost_t>::max());
                vector<size_t> queue(n);
                vector<size_t>::iterator head = queue.begin(), tail = std::next(head);
                inq[*head = source] = true;
                dcs[source] = 0;
                dis[source] = flow_max_v;
                while (head != tail){
                    size_t u = *head; ++head;
                    inq[u] = false;
                    for (size_t id : vertexs[u]){
                        size_t to = edges[id].to;
                        flow_t fl = edges[id].flow;
                        cost_t cs = edges[id].cost;
                        if (fl && dcs[to] > dcs[u] + cs){
                            dcs[to] = dcs[u] + cs, pre[to] = id;
                            dis[to] = std::min(dis[u], fl);
                            if (!inq[to]){
                                inq[to] = true;
                                if (__builtin_expect(tail == queue.end(), false)){
                                    size_t new_size = queue.size() << 1, count = tail - head;
                                    queue.erase(queue.begin(), head);
                                    if (new_size > uint64_t(n * n * n * 2))
                                        throw runtime_error("network_with_cost::EK_min_cost : Containing negative rings.");
                                    queue.resize(new_size);
                                    head = queue.begin();
                                    tail = head + count;
                                }
                                *tail = to, ++tail;
                            }
                        }
                    }
                }
                return dcs[sink] != std::numeric_limits<cost_t>::max();
            };
            flow_t max_flow = 0;
            cost_t min_cost = 0;
            while (spfa()){
                if (!flow_max && dcs[sink] > 0)break;
                max_flow += dis[sink];
                min_cost += dis[sink] * dcs[sink];
                for (size_t u = sink; u != source; u = edges[pre[u] ^ 1].to)
                    edges[pre[u]].flow -= dis[sink], edges[pre[u] ^ 1].flow += dis[sink];
            }
            return cost_and_flow(min_cost, max_flow);
        }

        cost_and_flow EK_max_cost(bool flow_max = true){
            size_t n = vertexs.size();
            vector<size_t> pre(n);
            vector<flow_t> dis(n);
            vector<cost_t> dcs(n);
            auto spfa = [&]{
                std::fill_n(dis.begin(), n, 0);
                basic_string<bool> inq; inq.resize(n);
                std::fill_n(pre.begin(), n, 0);
                std::fill_n(dcs.begin(), n, std::numeric_limits<cost_t>::lowest());
                vector<size_t> queue(n);
                vector<size_t>::iterator head = queue.begin(), tail = std::next(head);
                inq[*head = source] = true;
                dcs[source] = 0;
                dis[source] = flow_max_v;
                while (head != tail){
                    size_t u = *head; ++head;
                    inq[u] = false;
                    for (size_t id : vertexs[u]){
                        size_t to = edges[id].to;
                        flow_t fl = edges[id].flow;
                        cost_t cs = edges[id].cost;
                        if (fl && dcs[to] < dcs[u] + cs){
                            dcs[to] = dcs[u] + cs, pre[to] = id;
                            dis[to] = std::min(dis[u], fl);
                            if (!inq[to]){
                                inq[to] = true;
                                if (__builtin_expect(tail == queue.end(), false)){
                                    size_t new_size = queue.size() << 1, count = tail - head;
                                    queue.erase(queue.begin(), head);
                                    if (new_size > uint64_t(n * n * n * 2))
                                        throw runtime_error("network_with_cost::EK_max_cost : Containing positive rings.");
                                    queue.resize(new_size);
                                    head = queue.begin();
                                    tail = head + count;
                                }
                                *tail = to, ++tail;
                            }
                        }
                    }
                }
                return dcs[sink] != std::numeric_limits<cost_t>::lowest();
            };
            flow_t max_flow = 0;
            cost_t max_cost = 0;
            while (spfa()){
                if (!flow_max && dcs[sink] < 0)break;
                max_flow += dis[sink];
                max_cost += dis[sink] * dcs[sink];
                for (size_t u = sink; u != source; u = edges[pre[u] ^ 1].to)
                    edges[pre[u]].flow -= dis[sink], edges[pre[u] ^ 1].flow += dis[sink];
            }
            return cost_and_flow(max_cost, max_flow);
        }

        enum type {
            min_cost,
            max_cost
        };

        typedef cost_and_flow flow_result_t;

        cost_and_flow flow(type t, bool flow_max = true){
            return t == min_cost? EK_min_cost(flow_max) : EK_max_cost(flow_max);
        }

    };

    struct edge_without_weight {// 二分图中，0<=u<left 为左部点，0<=v<right 为右部点
        size_t u, v;
        edge_without_weight() : u(-1), v(-1) {}
        edge_without_weight(size_t x, size_t y) : u(x), v(y) {}
    };

    struct bipartite_graph_info {
        size_t left, right;
        size_t source, sink;
        network net;
        size_t middle_edge;//[0,middle_edge) -> middle
    };

    template <typename iter_t,
            typename = std::enable_if_t<std::is_same<typename std::iterator_traits<iter_t>::value_type, edge_without_weight>::value> >
        bipartite_graph_info bipartite_graph(size_t left, size_t right, iter_t edge_bg, iter_t edge_ed){
            bipartite_graph_info ret;
            ret.left = left, ret.right = right;
            ret.source = left + right, ret.sink = ret.source + 1;
            ret.net.set_vertex(left + right + 2, ret.source, ret.sink);
            for (; edge_bg != edge_ed; ++edge_bg)
                ret.net.add_edge(edge_bg->u, edge_bg->v + left);
            ret.middle_edge = ret.net.edges.size();
            for (size_t i = 0; i < left; ++i)ret.net.add_edge(ret.source, i);
            for (size_t i = 0; i < right; ++i)ret.net.add_edge(left + i, ret.sink);
            return ret;
        }

    // 二分图最大匹配 网络流
    vector<edge_without_weight> max_match_flow(bipartite_graph_info &bigr){// 返回匹配边
        vector<edge_without_weight> ret;
        ret.reserve(bigr.net.DINIC_max_flow());
        for (size_t i = 0; i != bigr.middle_edge; i += 2)
            if (bigr.net.edges[i ^ 1].flow)ret.emplace_back(bigr.net.edges[i ^ 1].to, bigr.net.edges[i].to - bigr.left);
        return ret;
    }

    // 匈牙利算法
    vector<edge_without_weight> max_match_km(bipartite_graph_info &bigr){// 返回匹配边
        vector<size_t> match(bigr.right, -1);
        vector<vector<size_t> > G(bigr.left);
        for (size_t i = 0; i != bigr.middle_edge; i += 2)
            G[bigr.net.edges[i ^ 1].to].emplace_back(bigr.net.edges[i].to - bigr.left);
        vector<size_t> vis(bigr.left, -1);
        auto find = [&](auto &&self, size_t left_point, size_t vis_time) -> bool {
            if (vis[left_point] == vis_time)return false;
            vis[left_point] = vis_time;
            for (size_t right_point : G[left_point])
                if (match[right_point] == (size_t)-1 || self(self, match[right_point], vis_time)){
                    match[right_point] = left_point;
                    return true;
                }
            return false;
        };
        for (size_t i = 0; i < bigr.left; ++i)find(find, i, i);
        vector<edge_without_weight> ret;
        for (size_t i = 0; i < bigr.right; ++i)
            if (~match[i])ret.emplace_back(match[i], i);
        return ret;
    }

    // 二分图最小点覆盖
    vector<size_t> minimum_point_coverage(bipartite_graph_info &bigr){
        //[0,left) and [left,left+right)
        bigr.net.DINIC_max_flow();
        basic_string<bool> inS; inS.resize(bigr.left + bigr.right);
        for (auto t : bigr.net.min_cut())inS[t] = true;
        vector<size_t> ret;
        for (size_t i = 0; i < bigr.left; ++i)if (!inS[i])ret.emplace_back(i);
        for (size_t i = bigr.left, _ = bigr.left + bigr.right; i < _; ++i)if (inS[i])ret.emplace_back(i);
        return ret;
    }

    // 二分图最大独立集
    vector<size_t> maximum_independent_set(bipartite_graph_info &bigr){
        //[0,left) and [left,left+right)
        bigr.net.DINIC_max_flow();
        basic_string<bool> inS; inS.resize(bigr.left + bigr.right);
        for (auto t : bigr.net.min_cut())inS[t] = true;
        vector<size_t> ret;
        for (size_t i = 0; i < bigr.left; ++i)if (inS[i])ret.emplace_back(i);
        for (size_t i = bigr.left, _ = bigr.left + bigr.right; i < _; ++i)if (!inS[i])ret.emplace_back(i);
        return ret;
    }

    template <typename iter_t,
            typename = std::enable_if_t<std::is_same<typename std::iterator_traits<iter_t>::value_type, edge_without_weight>::value> >
        vector<vector<size_t> > DAG_path_cover(size_t n, iter_t edge_bg, iter_t edge_ed){
            network net;
            size_t source = n << 1, sink = source + 1;
            net.set_vertex(sink + 1, source, sink);
            for (; edge_bg != edge_ed; ++edge_bg)
                net.add_edge(edge_bg->u, edge_bg->v + n);
            size_t mid = net.edges.size();
            for (size_t i = 0; i < n; ++i){
                net.add_edge(source, i);
                net.add_edge(i + n, sink);
            }
            vector<vector<size_t> > ret;
            ret.reserve(n - net.DINIC_max_flow());
            vector<vector<size_t> > G(n);
            vector<size_t> indegree(n);
            for (size_t i = 0; i < mid; i += 2)
                if (net.edges[i ^ 1].flow)
                    G[net.edges[i ^ 1].to].emplace_back(net.edges[i].to - n), ++indegree[net.edges[i].to - n];
            for (size_t i = 0; i < n; ++i)
                if (!indegree[i]){
                    ret.emplace_back();
                    size_t u = i;
                    ret.back().emplace_back(u);
                    while (!G[u].empty())
                        ret.back().emplace_back(u = G[u][0]);
                }
            return ret;
        }

    vector<size_t> max_match_must_pass_vertex(bipartite_graph_info &bigr){// 最大匹配必经点
        size_t n = bigr.net.vertexs.size();
        basic_string<bool> vs; vs.resize(n);
        auto dfs = [&](auto &&slf, size_t u, bool w) -> void {
            if (vs[u])return;
            vs[u] = 1;
            for (size_t id : bigr.net.vertexs[u])
                if (bigr.net.edges[id].flow == w)
                    slf(slf, bigr.net.edges[id].to, w);
        };
        vector<size_t> r;
        dfs(dfs, bigr.net.source, 1);// 从源点出发走流量等于 $1$ 的边所不能到达的左部点
        for (size_t i = 0; i < bigr.left; ++i)if (!vs[i])r.emplace_back(i);
        fill(vs.begin(), vs.end(), false);
        dfs(dfs, bigr.net.sink, 0);// 从汇点出发走流量等于 $0$ 的边所不能到达的右部点
        for (size_t i = 0; i < bigr.right; ++i)if (!vs[bigr.left + i])r.emplace_back(bigr.left + i);
        return r;
    }

    struct network_no_source_sink_with_bound {
        network net;
        size_t vsource, vsink;
        flow_t base;
        vector<signed_flow_t> in;
        network_no_source_sink_with_bound() : net{}, vsource{}, vsink{}, base{}, in{} {}
        #ifdef bound_flow_less_edge
        bool built;
        #endif
        void set_vertex(size_t n){
            vsource = n, vsink = n + 1;
            net.set_vertex(n + 2, vsource, vsink);
            in.assign(n + 2, 0);
            base = 0;
            #ifdef bound_flow_less_edge
            built = false;
            #endif
        }
        void clear(){
            set_vertex(0);
        }
        void reset_flow(){
            net.reset_flow();
        }
        #ifdef bound_flow_less_edge
        void add_edge(size_t from, size_t to, flow_t low, flow_t high){
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_no_source_sink_with_bound::add_edge : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low);
            if (low){
                in[from] -= low;
                in[to] += low;
                // net.add_edge(from, vsink, low);
                // net.add_edge(vsource, to, low);
            }
        }
        void add_edge_fixed(size_t from, size_t to, flow_t fixed_flow){
            add_edge(from, to, fixed_flow, fixed_flow);
        }
        void add_edge_norm(size_t from, size_t to, flow_t flow = 1){
            add_edge(from, to, 0, flow);
        }
        void build(){
            base = 0;
            for (size_t i = 0, _ = net.vertexs.size(); i < _; ++i){
                if (in[i] < 0)net.add_edge(i, vsink, -in[i]);
                if (in[i] > 0)net.add_edge(vsource, i, in[i]), base += in[i];
            }
        }
        #else
        void add_edge_nobuild(size_t from, size_t to, flow_t low, flow_t high){//无需调用 build
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_no_source_sink_with_bound::add_edge_nobuild : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low);
            if (low){
                net.add_edge(from, vsink, low);
                net.add_edge(vsource, to, low);
                base += low;
            }
        }
        #endif
        bool exists_flow(){
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            return net.DINIC_max_flow() == base;
        }
    };

    struct network_with_bound {
        network net;
        size_t vsource, vsink;
        size_t source, sink;
        flow_t base;
        vector<signed_flow_t> in;
        network_with_bound() : net{}, vsource{}, vsink{}, source{}, sink{}, base{}, in{} {}
        #ifdef bound_flow_less_edge
        bool built;
        #endif
        void set_vertex(size_t n, size_t S, size_t T){
            source = S, sink = T;
            vsource = n, vsink = n + 1;
            net.set_vertex(n + 2, vsource, vsink);
            in.assign(n + 2, 0);
            base = 0;
            net.add_edge(T, S, flow_max_v);
            #ifdef bound_flow_less_edge
            built = false;
            #endif
        }
        void clear(){
            set_vertex(0, 0, 0);
        }
        void reset_flow(){
            net.reset_flow();
        }
        #ifdef bound_flow_less_edge
        void add_edge(size_t from, size_t to, flow_t low, flow_t high){
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_with_bound::add_edge : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low);
            if (low){
                in[from] -= low;
                in[to] += low;
                // net.add_edge(from, vsink, low);
                // net.add_edge(vsource, to, low);
            }
        }
        void add_edge_fixed(size_t from, size_t to, flow_t fixed_flow){
            add_edge(from, to, fixed_flow, fixed_flow);
        }
        void add_edge_norm(size_t from, size_t to, flow_t flow = 1){
            add_edge(from, to, 0, flow);
        }
        void build(){
            base = 0;
            for (size_t i = 0, _ = net.vertexs.size(); i < _; ++i){
                if (in[i] < 0)net.add_edge(i, vsink, -in[i]);
                if (in[i] > 0)net.add_edge(vsource, i, in[i]), base += in[i];
            }
            built = true;
        }
        #else
        void add_edge_nobuild(size_t from, size_t to, flow_t low, flow_t high){//无需调用 build
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_with_bound::add_edge_nobuild : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low);
            if (low){
                net.add_edge(from, vsink, low);
                net.add_edge(vsource, to, low);
                base += low;
            }
        }
        #endif
        bool exists_flow(){
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            return net.DINIC_max_flow() == base;
        }
        pair<bool, flow_t> max_flow(){//(exists, flow)
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            if (!exists_flow())return make_pair(false, 0);
            flow_t fst = net.edges[1].flow;
            net.source = source, net.sink = sink;
            net.edges[0].flow = net.edges[1].flow = 0;
            return make_pair(true, fst + net.DINIC_max_flow());
        }
        pair<bool, flow_t> min_flow(){//(exists, flow)
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            if (!exists_flow())return make_pair(false, 0);
            flow_t fst = net.edges[1].flow;
            net.source = sink, net.sink = source;
            net.edges[0].flow = net.edges[1].flow = 0;
            return make_pair(true, fst - net.DINIC_max_flow());
        }
    };

    struct network_with_cost_and_bound {
        network_with_cost net;
        size_t vsource, vsink;
        size_t source, sink;
        flow_t base_flow;
        cost_t base_cost;
        vector<signed_flow_t> in;
        network_with_cost_and_bound() : net{}, vsource{}, vsink{}, source{}, sink{}, base_flow{}, base_cost{}, in{} {}
        #ifdef bound_flow_less_edge
        bool built;
        #endif
        void set_vertex(size_t n, size_t S, size_t T){
            source = S, sink = T;
            vsource = n, vsink = n + 1;
            net.set_vertex(n + 2, vsource, vsink);
            in.assign(n + 2, 0);
            base_flow = 0;
            base_cost = 0;
            net.add_edge(T, S, flow_max_v, 0);
            #ifdef bound_flow_less_edge
            built = false;
            #endif
        }
        void clear(){
            set_vertex(0, 0, 0);
        }
        void reset_flow(){
            net.reset_flow();
        }
        #ifdef bound_flow_less_edge
        void add_edge(size_t from, size_t to, flow_t low, flow_t high, cost_t cs){
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_with_cost_and_bound::add_edge : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low, cs);
            if (low){
                in[from] -= low;
                in[to] += low;
                // net.add_edge(from, vsink, low, 0);
                // net.add_edge(vsource, to, low, 0);
                base_cost += low * cs;
            }
        }
        void add_edge_fixed(size_t from, size_t to, flow_t fixed_flow, cost_t cs = 0){
            add_edge(from, to, fixed_flow, fixed_flow, cs);
        }
        void add_edge_norm(size_t from, size_t to, flow_t flow = 1, cost_t cs = 0){
            add_edge(from, to, 0, flow, cs);
        }
        void build(){
            base_flow = 0;
            for (size_t i = 0, _ = net.vertexs.size(); i < _; ++i){
                if (in[i] < 0)net.add_edge(i, vsink, -in[i], 0);
                if (in[i] > 0)net.add_edge(vsource, i, in[i], 0), base_flow += in[i];
            }
            built = true;
        }
        #else
        void add_edge_nobuild(size_t from, size_t to, flow_t low, flow_t high, cost_t cs){//无需调用 build
            if (!__builtin_expect(low <= high, true))
                throw runtime_error("network_with_cost_and_bound::add_edge_nobuild : The lower bound is higher than the upper bound.");
            if (high != low)net.add_edge(from, to, high - low, cs);
            if (low){
                net.add_edge(from, vsink, low, 0);
                net.add_edge(vsource, to, low, 0);
                base_cost += low * cs;
                base_flow += low;
            }
        }
        #endif
        pair<bool, cost_t> min_cost(){//feasible flow
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            cost_and_flow res = net.EK_min_cost();
            if (res.flow != base_flow)return make_pair(false, 0);
            net.source = source, net.sink = sink;
            net.edges[0].flow = net.edges[1].flow = 0;
            return make_pair(true, res.cost + net.EK_min_cost(false).cost);
        }
        pair<bool, cost_t> max_cost(){//feasible flow
            #ifdef bound_flow_less_edge
            assert(built);
            #endif
            cost_and_flow res = net.EK_max_cost();
            if (res.flow != base_flow)return make_pair(false, 0);
            net.source = source, net.sink = sink;
            net.edges[0].flow = net.edges[1].flow = 0;
            return make_pair(true, res.cost + net.EK_max_cost(false).cost);
        }
    };

}

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> r[100010];
int mt[100010];
bool md[100010];
bool mtd[100010];
pair<int, int> ed[100010];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    vector<flow_algo::edge_without_weight> edg;
    for (int i = 1, c, x; i < n; ++i){
        cin >> c;
        while (c--){
            int x;
            cin >> x;
            r[x].emplace_back(i);
            edg.emplace_back(x - 1, i - 1);
        }
    }
    auto G = flow_algo::bipartite_graph(n, n - 1, edg.begin(), edg.end());
    auto mtc = flow_algo::max_match_flow(G);
    if (mtc.size() < n - 1){
        cout << -1 << "\n";
        return 0;
    }
    for (auto [l, r] : mtc)mt[r + 1] = l + 1, mtd[l + 1] = 1;
    int ct = 0;
    auto dfs = [&](auto &&slf, int u) -> void {
        for (int v : r[u])if (!md[v]){
            md[v] = 1;
            ++ct;
            ed[v] = {u, mt[v]};
            slf(slf, mt[v]);
        }
    };
    dfs(dfs, find(mtd + 1, mtd + n + 1, 0) - mtd);
    if (ct != n - 1)cout << -1 << "\n";
    else for (int i = 1; i < n; ++i)cout << ed[i].first << " " << ed[i].second << "\n";
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'int main()':
./Main.cpp:819:24: warning: unused variable 'x' [-Wunused-variable]
  819 |     for (int i = 1, c, x; i < n; ++i){
      |                        ^
./Main.cpp:830:20: warning: comparison of integer expressions of different signedness: 'std::vector<flow_algo::edge_without_weight>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  830 |     if (mtc.size() < n - 1){
      |         ~~~~~~~~~~~^~~~~~~

ジャッジ結果