#662811 (Rust) No.957 植林

• 問題: No.957 植林
• ユーザー: SSlime
• 提出日時: 2021-06-03 20:30:27
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 710 ms / 2,000 ms
• コード長: 5,779 bytes
• コンパイル時間: 15,602 ms
• コンパイル使用メモリ: 377,528 KB
• 実行使用メモリ: 9,728 KB
• 最終ジャッジ日時: 2024-11-17 08:14:53
• 合計ジャッジ時間: 30,617 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	20 ms; 8,448 KB
testcase_04	AC	20 ms; 8,192 KB
testcase_05	AC	21 ms; 8,832 KB
testcase_06	AC	25 ms; 8,960 KB
testcase_07	AC	21 ms; 8,320 KB
testcase_08	AC	13 ms; 8,448 KB
testcase_09	AC	13 ms; 8,832 KB
testcase_10	AC	14 ms; 8,832 KB
testcase_11	AC	13 ms; 8,320 KB
testcase_12	AC	13 ms; 8,448 KB
testcase_13	AC	10 ms; 6,656 KB
testcase_14	AC	13 ms; 9,088 KB
testcase_15	AC	12 ms; 8,320 KB
testcase_16	AC	10 ms; 6,784 KB
testcase_17	AC	11 ms; 8,192 KB
testcase_18	AC	519 ms; 8,576 KB
testcase_19	AC	544 ms; 8,576 KB
testcase_20	AC	559 ms; 8,832 KB
testcase_21	AC	580 ms; 8,704 KB
testcase_22	AC	615 ms; 9,216 KB
testcase_23	AC	634 ms; 9,472 KB
testcase_24	AC	666 ms; 9,344 KB
testcase_25	AC	697 ms; 9,728 KB
testcase_26	AC	694 ms; 9,600 KB
testcase_27	AC	707 ms; 9,600 KB
testcase_28	AC	688 ms; 9,344 KB
testcase_29	AC	702 ms; 9,344 KB
testcase_30	AC	702 ms; 9,600 KB
testcase_31	AC	508 ms; 8,576 KB
testcase_32	AC	536 ms; 8,576 KB
testcase_33	AC	547 ms; 8,832 KB
testcase_34	AC	579 ms; 8,704 KB
testcase_35	AC	615 ms; 9,216 KB
testcase_36	AC	632 ms; 9,472 KB
testcase_37	AC	656 ms; 9,472 KB
testcase_38	AC	710 ms; 9,728 KB
testcase_39	AC	694 ms; 9,472 KB
testcase_40	AC	707 ms; 9,600 KB
testcase_41	AC	10 ms; 9,600 KB
testcase_42	AC	10 ms; 9,728 KB
testcase_43	AC	14 ms; 9,472 KB
testcase_44	AC	15 ms; 9,344 KB
testcase_45	AC	1 ms; 5,248 KB
testcase_46	AC	1 ms; 5,248 KB
testcase_47	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:134:5
    |
134 |     s.trim_end().to_owned();
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: cloning is often expensive and is not expected to have side effects
    = note: `#[warn(unused_must_use)]` on by default
help: use `let _ = ...` to ignore the resulting value
    |
134 |     let _ = s.trim_end().to_owned();
    |     +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:142:13
    |
142 |             s.trim_end().to_owned();
    |             ^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: cloning is often expensive and is not expected to have side effects
help: use `let _ = ...` to ignore the resulting value
    |
142 |             let _ = s.trim_end().to_owned();
    |             +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:154:5
    |
154 |     s.trim_end().to_owned();
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: cloning is often expensive and is not expected to have side effects
help: use `let _ = ...` to ignore the resulting value
    |
154 |     let _ = s.trim_end().to_owned();
    |     +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:164:5
    |
164 |     s.trim_end().to_owned();
    |     ^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: cloning is often expensive and is not expected to have side effects
help: use `let _ = ...` to ignore the resulting value
    |
164 |     let _ = s.trim_end().to_owned();
    |     +++++++

ソースコード

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

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() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_end().to_owned();
    let mut ws = s.split_whitespace();
    let h: usize = ws.next().unwrap().parse().unwrap();
    let w: usize = ws.next().unwrap().parse().unwrap();
    let g = (0..h)
        .map(|_| {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            s.trim_end().to_owned();
            let mut ws = s.split_whitespace();
            (0..w)
                .map(|_| {
                    let f: u64 = ws.next().unwrap().parse().unwrap();
                    f
                })
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>();
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_end().to_owned();
    let mut ws = s.split_whitespace();
    let r = (0..h)
        .map(|_| {
            let a: u64 = ws.next().unwrap().parse().unwrap();
            a
        })
        .collect::<Vec<_>>();
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_end().to_owned();
    let mut ws = s.split_whitespace();
    let c = (0..w)
        .map(|_| {
            let a: u64 = ws.next().unwrap().parse().unwrap();
            a
        })
        .collect::<Vec<_>>();
    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::<u64>());
        graph.add_edge(i+1, h+w+1, r[i]);
        s += r[i];
    }
    for j in 0..w {
        graph.add_edge(h+j+1, h+w+1, c[j]);
        s += c[j];
        for i in 0..h {
            graph.add_edge(i+1, h+j+1, g[i][j]);
        }
    }
    let f = graph.flow(0, h+w+1);
    println!("{}", s - f);
}