結果

問題 No.957 植林
ユーザー SSlimeSSlime
提出日時 2021-06-03 20:30:11
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 815 ms / 2,000 ms
コード長 5,801 bytes
コンパイル時間 17,776 ms
コンパイル使用メモリ 379,360 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2024-11-17 08:12:08
合計ジャッジ時間 33,247 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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,320 KB
testcase_05 AC 19 ms
8,960 KB
testcase_06 AC 24 ms
8,960 KB
testcase_07 AC 21 ms
8,320 KB
testcase_08 AC 13 ms
8,320 KB
testcase_09 AC 12 ms
8,960 KB
testcase_10 AC 14 ms
8,960 KB
testcase_11 AC 13 ms
8,576 KB
testcase_12 AC 12 ms
8,448 KB
testcase_13 AC 10 ms
6,816 KB
testcase_14 AC 13 ms
9,216 KB
testcase_15 AC 12 ms
8,320 KB
testcase_16 AC 10 ms
6,820 KB
testcase_17 AC 12 ms
8,192 KB
testcase_18 AC 516 ms
8,576 KB
testcase_19 AC 551 ms
8,448 KB
testcase_20 AC 557 ms
8,704 KB
testcase_21 AC 584 ms
8,832 KB
testcase_22 AC 619 ms
9,344 KB
testcase_23 AC 636 ms
9,344 KB
testcase_24 AC 667 ms
9,472 KB
testcase_25 AC 712 ms
9,728 KB
testcase_26 AC 705 ms
9,600 KB
testcase_27 AC 721 ms
9,728 KB
testcase_28 AC 696 ms
9,344 KB
testcase_29 AC 771 ms
9,600 KB
testcase_30 AC 815 ms
9,472 KB
testcase_31 AC 510 ms
8,448 KB
testcase_32 AC 547 ms
8,576 KB
testcase_33 AC 554 ms
8,832 KB
testcase_34 AC 588 ms
8,704 KB
testcase_35 AC 639 ms
9,216 KB
testcase_36 AC 636 ms
9,472 KB
testcase_37 AC 688 ms
9,600 KB
testcase_38 AC 718 ms
9,728 KB
testcase_39 AC 703 ms
9,600 KB
testcase_40 AC 712 ms
9,728 KB
testcase_41 AC 10 ms
9,472 KB
testcase_42 AC 10 ms
9,728 KB
testcase_43 AC 14 ms
9,472 KB
testcase_44 AC 16 ms
9,216 KB
testcase_45 AC 1 ms
6,816 KB
testcase_46 AC 1 ms
6,820 KB
testcase_47 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `proconio::input`
 --> src/main.rs:3:5
  |
3 | use proconio::input;
  |     ^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:136:5
    |
136 |     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
    |
136 |     let _ = s.trim_end().to_owned();
    |     +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:144:13
    |
144 |             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
    |
144 |             let _ = s.trim_end().to_owned();
    |             +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:156:5
    |
156 |     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
    |
156 |     let _ = s.trim_end().to_owned();
    |     +++++++

warning: unused return value of `to_owned` that must be used
   --> src/main.rs:166:5
    |
166 |     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
    |
166 |     let _ = s.trim_end().to_owned();
    |     +++++++

ソースコード

diff # 

// -*- 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() {
    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);
}
0