AOJ 1615 Gift Exchange Party - すいバカ日誌

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1615

解法

友人の助けを借りて解いた．

この問題は最大流の問題に帰着させることができる．（想定解は違う方法だった．）
まず，二部グラフ {V1, V2} をつくる．V1 は n 頂点からなり，各人を表す．V2 は m 頂点からなり，親しい友人関係を表す．
親しい友人関係 i が u, v (V1 の頂点) であるならば， u -> 関係 i, v -> 関係 i にそれぞれ容量 1 の辺をはる．
次に，source -> 各人に容量をいい感じに定めて辺をはる（これはあとで説明する）．
最後に，各関係 -> dest に容量 1 の辺をはる．
こうしでできたグラフに対し，source から dest にフローを流す．この時，source -> 各人の辺に流れている流量が，その人がもらえるプレゼントを表していることがわかる．

あとは，source -> 各人の容量をいい感じに定めていく．

プレゼントを一番多くもらえる人のプレゼントの数の最小値 x は，source ->
各人の辺の容量を小さい方から試していって，初めて m の流量が流れた(つまりプレゼントの受け渡しが完全に終わった)ときの容量に対応していることがわかる．

また，プレゼントを一番もらえない人のプレゼントの数の最大値 y は，source -> 各人の容量を c と定めた時，c * n の流量が流れるような c の最大値に対応することがわかる．
これは，最適な解の時のプレゼントの受け渡し方をフロー上で考えるとわかる．プレゼントを一番もらえない人のプレゼント数を k とすると，それ以外の人は必ず k 以上もらっている．つまり，source -> 各人の容量を k に絞ると，流量は n * k になるはずである．
さらに，このようにフローを流すと，その時の最大値は，先ほど求めた x に対応していることが明らかにわかる(平均的に流せるなら当然そうすべきなので）．

n が小さいので割りと適当に書いても通る．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
struct edge {
    int to, cap, rev;
};
 
using edges = std::vector<edge>;
using graph = std::vector<edges>;
 
void add_edge(graph& g, int from, int to, int cap) {
    g[from].push_back(edge{to, cap, static_cast<int>(g[to].size())});
    g[to].push_back(edge{from, 0, static_cast<int>(g[from].size()-1)});
}
 
int dfs(graph& g, std::vector<bool>& used, int v, int t, int f) {
    if(v == t) {
        return f;
    }
    used[v] = true;
    for(int i=0; i<g[v].size(); ++i) {
        edge& e = g[v][i];
        if(!used[e.to] && e.cap > 0) {
            int d = dfs(g, used, e.to, t, std::min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
 
int max_flow(graph& g, int s, int t) {
    int flow = 0;
    int INF = 1e9;
    std::vector<bool> used(g.size(), false);
    while(true) {
        std::fill(used.begin(), used.end(), false);
        int f = dfs(g, used, s, t, INF);
        if(f == 0) {
            return flow;
        }
        flow += f;
    }
 
}
 
int calc_max(int n, vector<int> const& u, vector<int> const& v) {
    const int m = u.size();
    graph g(n + m + 2);
    const int source = n + m;
    const int dest = n + m + 1;
    for(int i=0; i<m; ++i) {
        add_edge(g, u[i], n + i, 1);
        add_edge(g, v[i], n + i, 1);
        add_edge(g, n + i, dest, 1);
    }
    for(int i=0; i<n; ++i) {
        add_edge(g, source, i, 0);
    }
    int flow = 0;
    int res = 1;
    for(; ; ++res) {
        for(auto& e : g[source]) {
            e.cap += 1;
        }
        flow += max_flow(g, source, dest);
        if(flow == m) {
            break;
        }
    }
    return res;
}
 
int calc_min(int n, vector<int> const& u, vector<int> const& v) {
    const int m = u.size();
    graph g(n + m + 2);
    const int source = n + m;
    const int dest = n + m + 1;
    for(int i=0; i<m; ++i) {
        add_edge(g, u[i], n + i, 1);
        add_edge(g, v[i], n + i, 1);
        add_edge(g, n + i, dest, 1);
    }
    for(int i=0; i<n; ++i) {
        add_edge(g, source, i, 0);
    }
    int res = 0;
    int flow = 0;
    for(int i = 1; i <= 100; ++i) {
        for(auto& e : g[source]) {
            e.cap += 1;
        }
        flow += max_flow(g, source, dest);
        if(flow == n * i) {
            res = i;
        }
    }
    return res;
}
 
int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> u(m), v(m);
        for(int i=0; i<m; ++i) {
            cin >> u[i] >> v[i];
            u[i]--;
            v[i]--;
        }
        int ma = calc_max(n, u, v);
        int mi = calc_min(n, u, v);
        cout << mi << ' ' << ma << endl;
    }
}