ICPC国内予選2016 H問題 : プレゼント交換会

問題. プレゼント交換会

$n$ 頂点 $m$ 辺の無向グラフ $G$ が与えられる．入次数の最大値と最小値の差が小さくなるような各辺の向き付けを求めよ．最適解が複数ある場合は入次数の最小値が大きいものを選ぶとする．

制約： $2 \le n \le 100$ ，　 $1 \le m \le n (n - 1) / 2$

解法1. 下限制約付き最大流問題

入力グラフ $G = (V, E)$ の辺の向き付けで，次数の下限と上限がそれぞれ $l, u$ となるものが存在するかを判定する．そのために，次のようなネットワーク $H = (V', E')$ を構成して $H$ の下限制約付き最大流問題を解く．

$V' := \{v_u \mid u \in V\} \cup \{v_e \mid e \in E\} \cup \{s, t\}$
$E'_1 := \{s v_u \mid u \in V\},\, E'_2 := \{v_u v_e \mid v_u \in e \in E\},\, E_3 := \{v_e t \mid e \in E\}$
$E' := E'_1 \cup E'_2 \cup E'_3$

$H$ の各辺の容量制約の下限 ${\rm lb} : E' \rightarrow \mathbb{Z}_{+}$ と上限 ${\rm ub} : E' \rightarrow \mathbb{Z}_{+}$ をそれぞれ次のように定義する．

${\rm lb} (e) = l, \, {\rm ub} (e) = u \, \left(e \in E'_1 \right)$
${\rm lb}(e) = 0, \, {\rm ub}(e) = 1 \, \left(e \in E'_2 \cup E'_3 \right)$

$H$ の下限制約付き $s$ - $t$ 最大流問題の最適値が $m$ に等しい場合は，各次数が $l$ 以上 $u$ 以下となる $G$ の辺の向き付けが存在する．具体的には，流量が1となる辺 $v_u v_e \in E'_2$ に対して， $G$ 上の辺 $e$ を頂点 $u$ を向くようすればよい．後は， $l, u$ の値を尺取り法で探索すれば答えが求まる．
下限制約付き最大流問題は [2] を参考に最大流問題に帰着して Dinic法で求めた．

計算時間： $O(n^7)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template<typename Weight>
class Dinic {
public:
    Dinic(const int n) : n(n), g(n), INF(numeric_limits<Weight>::max()) {}

    void add_edge(const int src, const int dst, const Weight cap) {
        g[src].emplace_back(Edge(src, dst, cap, g[dst].size()));
        g[dst].emplace_back(Edge(dst, src, 0, g[src].size() - 1));
    }

    // O(|E||V|^2)
    Weight MaximumFlow(const int s, const int t) {
        Weight flow = 0;

        while(true) {
            vector<int> level(n, -1), iter(n);
            Bfs(s, level);
            if(level[t] == -1) break;
            for (Weight f = 0; (f = Dfs(s, t, INF, level, iter)) > 0; )
                flow += f;
        }

        return flow;
    }

private:
    struct Edge {
        int src, dst, rev;
        Weight weight;
        Edge(int f, int t, Weight cap, int rev = 0) :
            src(f), dst(t), rev(rev), weight(cap) {}
    };

    int n;
    vector<vector<Edge>> g;
    const Weight INF;

    void Bfs(const int s, vector<int> &level){
        queue<int> que;
        for (level[s] = 0, que.push(s); !que.empty(); ) {
            const int v = que.front(); que.pop();
            for (auto &e : g[v])
                if(0 < e.weight && level[e.dst] == -1){
                    level[e.dst] = level[v] + 1;
                    que.push(e.dst);
                }
        }
    }

    Weight Dfs(int v, int t, Weight flow, vector<int> &level, vector<int> &iter) {
        if(v == t) return flow;
        for ( ; iter[v] < (int)g[v].size(); ++iter[v]) {
            Edge &e = g[v][iter[v]];

            if(0 < e.weight && level[v] < level[e.dst]){
                Weight d = Dfs(e.dst, t, min(flow, e.weight), level, iter);
                if(0 < d){
                    e.weight -= d;
                    g[e.dst][e.rev].weight += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

template<class Weight>
class DinicWithLowerBound {
public:
    DinicWithLowerBound(int n) : dinic(n + 2), n(n), S(n), T(n + 1), sum_lb(0) {}

    void add_edge(const int src, const int dst, const int lb, const int ub) {
        if (src == dst || ub == 0) return ;
        dinic.add_edge(src, dst, ub - lb);
        dinic.add_edge(S, dst, lb);
        dinic.add_edge(src, T, lb);
        sum_lb += lb;
    }
    Weight MaximumFlow(const int s, const int t) {
        const Weight f1 = dinic.MaximumFlow(S, T);
        const Weight f2 = dinic.MaximumFlow(s, T);
        const Weight f3 = dinic.MaximumFlow(S, t);
        const Weight f4 = dinic.MaximumFlow(s, t);
        return (f1 + f3 == sum_lb && f1 + f2 == sum_lb) ? f2 + f4 : -1;
    }

private:
    Dinic<Weight> dinic;
    int n, S, T;
    Weight sum_lb;
};

bool Feasible(const int lb, const int ub, const int n, const int m,
              const int s, const int t, auto dinic) {
    for (int v = 0; v < n; ++v)
        dinic.add_edge(s, v, lb, ub);

    return dinic.MaximumFlow(s, t) == m;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, m, u, v;

    while (cin >> n >> m, n) {
        // [0, n) : 頂点集合，[n, n + m) : 辺集合, n + m : ソース，n + m + 1 : シンク
        DinicWithLowerBound<int> dinic(n + m + 2);
        const int s = n + m, t = n + m + 1;

        for (int i = n; i < n + m; ++i)
            dinic.add_edge(i, t, 0, 1);
        for (int i = 0; i < m; ++i) {
            cin >> u >> v;
            dinic.add_edge(u - 1, n + i, 0, 1);
            dinic.add_edge(v - 1, n + i, 0, 1);
        }

        pair<int, int> ans(0, n);
        int ub = 1;
        for (int lb = 0; lb <= ub && ub < n; ++lb) {
            while (ub < n && !Feasible(lb, ub, n, m, s, t, dinic)) ++ub;

            if (ub - lb < ans.second - ans.first)
                ans = make_pair(lb, ub);
        }

        cout << ans.first << ' ' << ans.second << '\n';
    }

    return 0;
}

解法2. 貪欲法

講評 [1] の貪欲法を実装した．次の2つの規則が適用できなくなるまで繰り返す．規則1は $d(v_0)$ を1増やし $d(v_i)$ を1減らす．また，規則2は $d(v_0)$ を1減らし $d(v_i)$ を1増やすことが出来る．

最小次数の頂点 $v_0$ から $d(v_0) + 2 \le d(v_i)$ を満たす頂点 $v_i$ まで有向辺に従いながら移動して有向辺を逆向きにする
最大次数の頂点 $v_0$ から $d(v_0) - 2 \ge d(v_i)$ を満たす頂点 $v_i$ まで有向辺の逆向きに従いながら移動して有向辺を逆向きにする

計算時間： $O(n^2 m)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int src, dst, rev;
    bool in;
    Edge(int s, int d, bool in, int rev = 0) :
        src(s), dst(d), rev(rev), in(in) {}
};

class GiftExchangeParty {
public:
    GiftExchangeParty(int n, int m) : n(n), m(m), g(n), deg(n) {}

    // src から dst へ向き付けを行う
    void add_edge(const int src, const int dst, const bool in) {
        g[src].emplace_back(Edge(src, dst, in, g[dst].size()));
        g[dst].emplace_back(Edge(dst, src, !in, g[src].size() - 1));
        ++deg[dst];
    }

    pair<int, int> MinimumDiff() {
        vector<bool> visited(n, false);

        while (true) {
            int min_idx = distance(deg.begin(), min_element(deg.begin(), deg.end()));
            int max_idx = distance(deg.begin(), max_element(deg.begin(), deg.end()));

            fill(visited.begin(), visited.end(), false);
            if (Dfs(min_idx, deg[min_idx] + 2, -1, true, visited)) continue;

            min_idx = distance(deg.begin(), min_element(deg.begin(), deg.end()));
            max_idx = distance(deg.begin(), max_element(deg.begin(), deg.end()));

            fill(visited.begin(), visited.end(), false);
            if (!Dfs(max_idx, -1, deg[max_idx] - 2, false, visited)) break;
        }

        return {*min_element(deg.begin(), deg.end()), *max_element(deg.begin(), deg.end())};
    }

private:
    int n, m;
    vector<vector<Edge>> g;
    vector<int> deg; // 入次数

    bool Dfs(const int cur, const int lb, const int ub, bool dir, vector<bool> &visited) {
        if (visited[cur]) return false;
        if ((!dir && deg[cur] <= ub) || (dir && lb <= deg[cur])) return true;

        visited[cur] = true;
        for (auto &e : g[cur]) {
            if (e.in == dir && Dfs(e.dst, lb, ub, dir, visited)) {
                if (dir) { // min
                    ++deg[e.src]; --deg[e.dst];
                    e.in = false; g[e.dst][e.rev].in = true;
                }
                else { // max
                    --deg[e.src]; ++deg[e.dst];
                    e.in = true; g[e.dst][e.rev].in = false;
                }
                return true;
            }
        }

        return false;
    }
};


int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, m, u, v;

    while (cin >> n >> m, n) {
        GiftExchangeParty prob(n, m);

        for (int i = 0; i < m; ++i) {
            cin >> u >> v;
            prob.add_edge(u - 1, v - 1, true);
        }

        auto ans = prob.MinimumDiff();
        cout << ans.first << ' ' << ans.second << '\n';
    }

    return 0;
}