competitive-programing

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Astral-23/competitive-programing

:heavy_check_mark: verify/maxflow_lowerbound.test.cpp

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615"
#include "../Utility/template.hpp"
#include "../Algorithm/maxflow.hpp"
#include "../Algorithm/maxflow_lowerbound.hpp"


using pll = pair<ll, ll>;

int main() {
    int n, m;
    while (1) {
        cin >> n >> m;

        if (n == 0) break;

        vector<pll> es;
        rep(i, 0, m) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            es.emplace_back(u, v);
        }

        int ans_m = -1;
        int ans_M = -1;

        auto che = [&](int mi, int Mi) {
            int s = n + m;
            int t = s + 1;

            mf_graph_with_lowerbound mf(t + 1);

            rep(i, 0, m) {
                mf.add_edge(s, i, 1, 1);
                mf.add_edge(i, m + es[i].first, 0, 1);
                mf.add_edge(i, m + es[i].second, 0, 1);
            }

            rep(i, 0, n) { mf.add_edge(m + i, t, mi, Mi); }

            if (mf.is_feasable(s, t)) {
                return true;
            } else
                return false;
        };

        ll w = 1e7;
        rrep(mi, 0, n + 1) {
            ll li = 0;
            ll ri = li + min<ll>(w, m);
            while (li < ri) {  /// xxxxoooo
                ll mid = (li + ri) / 2;
                if (che(mi, mi + mid)) {
                    ri = mid;
                } else {
                    li = mid + 1;
                }
            }
            if (che(mi, mi + li) && chmin(w, li - mi)) {
                ans_m = mi;
                ans_M = mi + li;
            }
        }

        cout << ans_m << " " << ans_M << endl;
    }
}
#line 1 "verify/maxflow_lowerbound.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/maxflow.hpp"
template <class T> struct mf_graph {
    struct edge {
        int st, to;
        T cap, flow;
    };

    struct nedge {
        int to, rev;
        T cap;
    };

    int n;
    vec<unordered_map<int, int>> rev;
    vec<pair<int, int>> pos;
    vec<vec<nedge>> g;

    mf_graph(int _n) : n(_n), g(n), rev(n) {}

    int add_edge(int s, int t, T cap) {
        int m = pos.size();
        pos.push_back({s, g[s].size()});
        int fi = g[s].size();
        int ti = g[t].size();
        if (s == t) ti++;
        g[s].push_back(nedge{t, ti, cap});
        g[t].push_back(nedge{s, fi, 0});
        rev[s][t] = m;
        return m;
    }

    T flow(int s, int t, T flow_limit = numeric_limits<T>::max()) {
        vec<int> lv(n), it(n, 0);

        auto bfs = [&]() {
            queue<int> que;
            fill(lv.begin(), lv.end(), -1);
            lv[s] = 0;
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();

                for (auto e : g[v]) {
                    if (e.cap == 0 || lv[e.to] >= 0) continue;
                    lv[e.to] = lv[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        };

        auto dfs = [&](auto f, int v, T up) {
            if (v == s) return up;
            T res = 0;
            int LV = lv[v];
            for (int &i = it[v]; i < int(g[v].size()); i++) {
                nedge &e = g[v][i];
                if (LV <= lv[e.to] || g[e.to][e.rev].cap == 0) continue;
                T d = f(f, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            lv[v] = n;
            return res;
        };

        T flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (lv[t] == -1) break;
            fill(it.begin(), it.end(), 0);
            T f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    // 以下、不要なら省略

    int get_id(int s, int t) { return rev[s][t]; }

    edge get_edge(int i) {
        int m = pos.size();
        auto e = g[pos[i].first][pos[i].second];
        auto re = g[e.to][e.rev];
        return edge{pos[i].first, e.to, e.cap + re.cap, re.cap};
    }

    void change_edge(int i, T nc, T nf) {
        int m = pos.size();
        auto &e = g[pos[i].first][pos[i].second];
        auto &re = g[e.to][e.rev];
        e.cap = nc - nf;
        re.cap = nf;
    }

    vec<bool> min_cut(int s) {
        vec<bool> seen(n);
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            seen[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !seen[e.to]) {
                    seen[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return seen;
    }
};

/*
@brief Maxflow
@docs doc/maxflow.md
*/
#line 1 "Algorithm/maxflow_lowerbound.hpp"
struct mf_graph_with_lowerbound {
    int n;
    mf_graph<ll> mf;  // atcoder::mf_graphでも良い。
    int S, T;
    ll sum;
    vector<ll> lows, d;
    ll total_flow;

    mf_graph_with_lowerbound(int n)
        : n(n), mf(n + 2), S(n), T(n + 1), sum(0), d(n, 0), total_flow(0) {}

    int add_edge(int from, int to, ll low, ll high) {
        lows.push_back(low);
        d[from] -= low;
        d[to] += low;
        return mf.add_edge(from, to, high - low);
    }

    void build() {
        rep(i, 0, n) {
            if (d[i] > 0) {
                mf.add_edge(S, i, d[i]);
                sum += d[i];
            } else
                mf.add_edge(i, T, -d[i]);
        }
    }

    bool is_feasable(int s, int t) {
        build();
        mf.add_edge(t, s, LLONG_MAX / 4);  // INF = LLONG_MAX / 4
        total_flow += mf.flow(S, T);
        return total_flow == sum;
    }

    ll flow(int s, int t) {
        if (is_feasable(s, t) == false) return -1;
        mf.add_edge(S, s, LLONG_MAX / 4);
        mf.add_edge(t, T, LLONG_MAX / 4);
        return (total_flow += mf.flow(S, T)) - sum;
    }

    vector<ll> output() {  // not verified
        vector<ll> res;
        rep(i, 0, lows.size()) { res.push_back(lows[i] + mf.get_edge(i).flow); }
        return res;
    }
};
#line 5 "verify/maxflow_lowerbound.test.cpp"


using pll = pair<ll, ll>;

int main() {
    int n, m;
    while (1) {
        cin >> n >> m;

        if (n == 0) break;

        vector<pll> es;
        rep(i, 0, m) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            es.emplace_back(u, v);
        }

        int ans_m = -1;
        int ans_M = -1;

        auto che = [&](int mi, int Mi) {
            int s = n + m;
            int t = s + 1;

            mf_graph_with_lowerbound mf(t + 1);

            rep(i, 0, m) {
                mf.add_edge(s, i, 1, 1);
                mf.add_edge(i, m + es[i].first, 0, 1);
                mf.add_edge(i, m + es[i].second, 0, 1);
            }

            rep(i, 0, n) { mf.add_edge(m + i, t, mi, Mi); }

            if (mf.is_feasable(s, t)) {
                return true;
            } else
                return false;
        };

        ll w = 1e7;
        rrep(mi, 0, n + 1) {
            ll li = 0;
            ll ri = li + min<ll>(w, m);
            while (li < ri) {  /// xxxxoooo
                ll mid = (li + ri) / 2;
                if (che(mi, mi + mid)) {
                    ri = mid;
                } else {
                    li = mid + 1;
                }
            }
            if (che(mi, mi + li) && chmin(w, li - mi)) {
                ans_m = mi;
                ans_M = mi + li;
            }
        }

        cout << ans_m << " " << ans_M << endl;
    }
}
Back to top page