#662807 (Rust) No.957 植林

• 問題: No.957 植林
• ユーザー: SSlime
• 提出日時: 2021-06-03 20:23:56
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 670 ms / 2,000 ms
• コード長: 4,647 bytes
• コンパイル時間: 14,498 ms
• コンパイル使用メモリ: 379,152 KB
• 実行使用メモリ: 10,752 KB
• 最終ジャッジ日時: 2024-11-17 07:33:19
• 合計ジャッジ時間: 30,353 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 45

ソースコード

// -*- coding:utf-8-unix -*-

use proconio::input;

use max_flow::MfGraph;

#[allow(dead_code)]
mod max_flow {
    struct _Edge {
        to: usize,
        rev: usize,
        cap: u64,
    }
    pub struct MfGraph {
        n: usize,
        pos: Vec<(usize, usize)>,
        g: Vec<Vec<_Edge>>
    }
    impl MfGraph {
        pub fn new(n: usize) -> MfGraph {
            MfGraph {
                n,
                pos: Vec::new(),
                g: (0..n).map(|_| Vec::new()).collect(),
            }
        }
        pub fn add_edge(&mut self, from: usize, to: usize, cap: u64) {
            let rev = self.g[to].len();
            self.g[from].push(_Edge {to, cap, rev});
            let rev = self.g[from].len() - 1;
            self.g[to].push(_Edge {to: from, cap: 0, rev});
        }
        pub fn flow(&mut self, s: usize, t: usize) -> u64 {
            self.flow_with_cap(s, t, u64::max_value())
        }
        pub fn flow_with_cap(&mut self, s: usize, t: usize, limit: u64) -> u64 {
            assert!(s < self.n && t < self.n);
            let n = self.n;
            let mut solver = FlowSolver {
                graph: self,
                s,
                t,
                limit,
                level: vec![0; n],
                iter: vec![0; n],
            };
            let mut flow = 0;
            while flow < limit {
                solver.bfs();
                if solver.level[t] == -1 {
                    break;
                }
                solver.iter.iter_mut().for_each(|e| *e = 0);
                while flow < limit {
                    let f = solver.dfs(s, limit - flow);
                    if f == 0 {
                        break;
                    }
                    flow += f;
                }
            }
            flow
        }
        pub fn min_cut(&mut self, s: usize) -> Vec<bool> {
            let mut visited = vec![false; self.n];
            let mut que = std::collections::VecDeque::new();
            que.push_back(s);
            while let Some(p) = que.pop_front() {
                visited[p] = true;
                for e in &self.g[p] {
                    if e.cap != 0 && !visited[e.to] {
                        visited[e.to] = true;
                        que.push_back(e.to);
                    }
                }
            }
            visited
        }
    }
    struct FlowSolver<'a> {
        graph: &'a mut MfGraph,
        s: usize,
        t: usize,
        limit: u64,
        level: Vec<i32>,
        iter: Vec<usize>,
    }
    impl FlowSolver<'_> {
        fn bfs(&mut self) {
            self.level.iter_mut().for_each(|e| *e = -1);
            self.level[self.s] = 0;
            let mut que = std::collections::VecDeque::<usize>::new();
            que.push_back(self.s);
            while let Some(now) = que.pop_front() {
                for &_Edge {to, cap, ..} in &self.graph.g[now] {
                    if cap <= 0 || self.level[to] >= 0 {continue;}
                    self.level[to] = self.level[now] + 1;
                    if self.t == to {
                        return;
                    }
                    que.push_back(to);
                }
            }
        }
        fn dfs(&mut self, v: usize, up: u64) -> u64 {
            if v == self.t {
                return up;
            }
            for i in self.iter[v]..self.graph.g[v].len() {
                self.iter[v] = i;
                let &_Edge {
                    to,
                    rev,
                    cap
                } = &self.graph.g[v][i];
                if cap <= 0 || self.level[v] >= self.level[to] {
                    continue;
                }
                let d = self.dfs(to, up.min(cap));
                if d <= 0 {
                    continue;
                }
                self.graph.g[v][i].cap -= d;
                self.graph.g[to][rev].cap += d;
                return d;
            }
            self.iter[v] = self.graph.g[v].len();
            0
        }
    }
}

fn main() {
    input! {
        h: usize,
        w: usize,
        g: [[i64; w]; h],
        r: [i64; h],
        c: [i64; w],
    }
    let mut graph = MfGraph::new(h+w+2);
    let mut s = 0;
    for i in 0..h {
        graph.add_edge(0, i+1, (&g[i]).into_iter().sum::<i64>() as u64);
        graph.add_edge(i+1, h+w+1, r[i] as u64);
        s += r[i] as u64;
    }
    for j in 0..w {
        graph.add_edge(h+j+1, h+w+1, c[j] as u64);
        s += c[j] as u64;
        for i in 0..h {
            graph.add_edge(i+1, h+j+1, g[i][j] as u64);
        }
    }
    let f = graph.flow(0, h+w+1);
    println!("{}", s - f);
}