最大流

[tipstar0125]

問題：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bp 解答：https://atcoder.jp/contests/tessoku-book/submissions/49271888

[tipstar0125]

#[derive(Debug, Clone)]
struct Edge {
    to: usize,
    cap: usize,
    rev: usize,
}

#[derive(Debug, Clone)]
struct MaximumFlow {
    size: usize,
    G: Vec<Vec<Edge>>,
}

impl MaximumFlow {
    fn new(n: usize) -> Self {
        MaximumFlow {
            size: n,
            G: vec![vec![]; n],
        }
    }
    fn add(&mut self, u: usize, v: usize, c: usize) {
        let u_size = self.G[u].len();
        let v_size = self.G[v].len();
        self.G[u].push(Edge {
            to: v,
            cap: c,
            rev: v_size,
        });
        self.G[v].push(Edge {
            to: u,
            cap: 0,
            rev: u_size,
        });
    }
    fn dfs(&mut self, pos: usize, goal: usize, F: usize, used: &mut Vec<bool>) -> usize {
        if pos == goal {
            return F;
        }
        used[pos] = true;

        for i in 0..self.G[pos].len() {
            if self.G[pos][i].cap == 0 {
                continue;
            }
            if used[self.G[pos][i].to] {
                continue;
            }
            let flow = self.dfs(self.G[pos][i].to, goal, F.min(self.G[pos][i].cap), used);
            if flow > 0 {
                self.G[pos][i].cap -= flow;
                let to = self.G[pos][i].to;
                let rev = self.G[pos][i].rev;
                self.G[to][rev].cap += flow;
                return flow;
            }
        }
        0
    }
    fn max_flow(&mut self, s: usize, t: usize) -> usize {
        let mut total_flow = 0;
        loop {
            let mut used = vec![false; self.size];
            let flow = self.dfs(s, t, std::usize::MAX, &mut used);
            if flow == 0 {
                break;
            }
            total_flow += flow;
        }
        total_flow
    }
}

[tipstar0125]

二部マッチング 問題：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bq 解答：https://atcoder.jp/contests/tessoku-book/submissions/49272049