graph.maxflow

graph.maxflow.rs

Dinic 法の実装

mod dinic {
    use std::collections::VecDeque;
    use std::cmp::min;

    pub type Weight = i32;
    pub type WeightedGraph = Vec<Vec<(usize, Weight)>>; // [u][] = (v, w)
    pub type Edge = (usize, usize, Weight);

    pub fn new(n: usize, es: &Vec<Edge>) -> WeightedGraph {
        let mut g: WeightedGraph = vec![vec![]; n];
        for &(u, v, w) in es.iter() {
            g[u].push((v, w));
            g[v].push((u, 0));
        }
        g
    }

    fn levelize(g: &WeightedGraph, s: usize, t: usize, cap: &Vec<Vec<Weight>>, flw: &Vec<Vec<Weight>>) -> Vec<i32> {
        let n = g.len();
        let mut level = vec![-1; n];
        let mut q = VecDeque::new(); q.push_back(s);
        while let Some(u) = q.pop_front() {
            if u == t { break }
            for &(v, _) in g[u].iter() {
                if level[v] == -1 && cap[u][v] - flw[u][v] != 0 {
                    level[v] = level[u] + 1;
                    q.push_back(v);
                }
            }
        }
        level
    }

    fn augment(limit: Weight,
               level: &Vec<i32>, mut used: &mut Vec<bool>,
               g: &WeightedGraph, u: usize, t: usize,
               cap: &Vec<Vec<Weight>>, mut flw: &mut Vec<Vec<Weight>>) -> Weight {
        if u == t {
            limit
        } else if used[u] || limit == 0 {
            0
        } else {
            used[u] = true;
            for &(v, _) in g[u].iter() {
                if level[v] > level[u] {
                    let limit2 = min(limit, cap[u][v] - flw[u][v]);
                    let f = augment(limit2, &level, &mut used, &g, v, t, &cap, &mut flw);
                    if f > 0 {
                        flw[u][v] += f; flw[v][u] -= f;
                        used[u] = false;
                        return f;
                    }
                }
            }
            0
        }
    }

    pub fn flow(g: &WeightedGraph, s: usize, t: usize) -> Weight {

        let n = g.len();

        let mut cap = vec![vec![0; n]; n];
        let mut flw = vec![vec![0; n]; n];
        for u in 0..n { for &(v, w) in g[u].iter() { cap[u][v] = w; } }

        let inf = Weight::max_value() / 8;
        let mut sum = 0;
        loop {
            let level = levelize(&g, s, t, &cap, &flw);
            if level[t] == -1 { break }
            let mut used = vec![false; n];
            sum += augment(inf, &level, &mut used, &g, s, t, &cap, &mut flw);
        }
        sum
    }
}

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let m: usize = sc.cin();

    let mut edges = vec![];
    for _ in 0..m {
        let u = sc.cin::<usize>() - 1;
        let v = sc.cin::<usize>() - 1;
        let w: dinic::Weight = sc.cin();
        edges.push((u, v, w));
    }

    let g = dinic::new(n, &edges);
    let max_flow = dinic::flow(&g, 0, n - 1);
    put!(max_flow);
}

graph.maxflow.cc

Ford-Fulkerson 法の実装

struct MaxFlow {
  int n;
  vvi d, c;
  vector<int> level, iter;
  int flow;

  MaxFlow(vvi& _d, vvi& _c, int s, int t) {
    d = _d; c = _c;
    n = _d.size();
    level.resize(n);
    iter.resize(n);
    int cur_flow = 0;
    loop {
      bfs(s);
      if (level[t] < 0) { flow = cur_flow; return; }
      rep (i, n) iter[i] = 0;
      for (int f = 0;;) {
        f = dfs(s, t, inf);
        if (f <= 0) break;
        cur_flow += f;
      }
    }
  }

  int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int i = iter[v]; i < d[v].size(); ++i) {
      int u = d[v][i]; // v -> u
      if (c[v][u] > 0 and level[v] < level[u]) {
        int d = dfs(u, t, min(f, c[v][u]));
        if (d > 0) {
          c[v][u] -= d;
          c[u][v] += d;
          return d;
        }
      }
    }
    return 0;
  }

  void bfs(int s) {
    rep (i, n) level[i] = i == s ? 0 : -1;
    queue<int> q; q.push(s);
    while (not q.empty()) {
      int u = q.front(); q.pop();
      for (auto&v: d[u]) { // u -> v
        if (c[u][v] > 0 and level[v] < 0) {
          level[v] = level[u] + 1;
          q.push(v);
        }
      }
    }
  }
};

Example

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout.setf(ios::fixed);
  cout.precision(10);

  stringstream input(
"  7"
"  0 6"
"  1 2"
"  1 4"
"  3 2"
"  5 2"
"  5 4"
"  0 1"
"  0 3"
"  0 5"
"  2 6"
"  4 6");
  int answer = 2;

  {
    int n; input >> n;
    int s, t; input >> s >> t;
    vvi d(n, vi(n));
    vvi c(n, vi(n, 0));
    loop {
      int a, b; input >> a >> b;
      if (not input) break;
      d[a].push_back(b);
      c[a][b] = 1;
    }
    MaxFlow mf(d, c, s, t);
    cout << mf.flow << endl;
    assert(mf.flow == answer);
  }

  stringstream input2(
"  6"
"  0 5"
"  0 1 3"
"  0 2 3"
"  1 2 2"
"  1 3 3"
"  2 4 2"
"  3 4 4"
"  3 5 2"
"  4 5 3");
  int answer2 = 5;
  {
    int n; input2 >> n;
    int s, t; input2 >> s >> t;
    vvi neighbor_list(n, vi(n));
    vvi capacity_table(n, vi(n, 0));
    loop {
      int a, b, c; input2 >> a >> b >> c;
      if (not input2) break;
      neighbor_list[a].push_back(b);
      capacity_table[a][b] = c;
    }
    MaxFlow mf(neighbor_list, capacity_table, s, t);
    cout << mf.flow << endl;
    assert(mf.flow == answer2);
  }
      

  return 0;
}

関連問題