Ford Fulkerson
(graph/ford-fulkerson/src/lib.rs)

• View this file on GitHub
• Last update: 2025-05-26 22:58:00+09:00

Description

Verified with

• verification/aizu-online-judge/grl_6_a/src/main.rs

Code

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

impl Edge {
    pub fn new(to: usize, cap: i64, rev: usize) -> Self {
        Self { to, cap, rev }
    }
}

#[derive(Debug, Clone)]
pub struct FordFulkerson {
    size: usize,
    used: Vec<bool>,
    graph: Vec<Vec<Edge>>,
}

impl FordFulkerson {
    pub fn new(size: usize) -> Self {
        Self {
            size,
            used: vec![false; size],
            graph: vec![vec![]; size],
        }
    }

    pub fn add_edge(&mut self, a: usize, b: usize, c: i64) {
        let alen = self.graph[a].len();
        let blen = self.graph[b].len();
        self.graph[a].push(Edge::new(b, c, blen));
        self.graph[b].push(Edge::new(a, 0, alen));
    }

    pub fn flow(&mut self, s: usize, t: usize) -> i64 {
        let mut total_flow = 0;
        loop {
            for i in 0..self.size {
                self.used[i] = false;
            }
            let flow = self.dfs(s, t, i64::MAX);
            if flow == 0 {
                break;
            }
            total_flow += flow;
        }
        total_flow
    }

    fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
        if v == t {
            return f;
        }
        self.used[v] = true;
        for i in 0..self.graph[v].len() {
            let u = self.graph[v][i];
            if u.cap == 0 {
                continue;
            }
            if self.used[u.to] {
                continue;
            }
            let flow = self.dfs(u.to, t, f.min(u.cap));
            if flow > 0 {
                self.graph[v][i].cap -= flow;
                self.graph[u.to][u.rev].cap += flow;
                return flow;
            }
        }
        0
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page