結果

問題 No.957 植林
ユーザー akakimidoriakakimidori
提出日時 2021-10-07 23:28:23
言語 Rust
(1.77.0)
結果
TLE  
実行時間 -
コード長 3,845 bytes
コンパイル時間 3,368 ms
コンパイル使用メモリ 154,776 KB
実行使用メモリ 12,692 KB
最終ジャッジ日時 2023-09-30 09:07:05
合計ジャッジ時間 10,708 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
8,756 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://37zigen.com/fujishige/

pub struct Fujishige {
    size: usize,
    graph: Vec<Vec<(usize, i64, usize)>>,
}

impl Fujishige {
    pub fn new(size: usize) -> Self {
        Self {
            size: size,
            graph: vec![vec![]; size],
        }
    }
    pub fn add_edge(&mut self, src: usize, dst: usize, capa: i64) {
        assert!(src != dst);
        assert!(src < self.size && dst < self.size);
        let x = self.graph[src].len();
        let y = self.graph[dst].len();
        self.graph[src].push((dst, capa, y));
        self.graph[dst].push((src, 0, x));
    }
    pub fn flow(&mut self, src: usize, dst: usize) -> i64 {
        assert!(src != dst);
        assert!(src < self.size && dst < self.size);
        let size = self.size;
        let mut f = 2i64.pow(29);
        let mut sum = vec![0; size];
        let mut topo = Vec::with_capacity(size);
        let mut used = vec![false; size];
        let mut pass = vec![0i64; size];
        while f > 0 {
            used.iter_mut().for_each(|u| *u = false);
            used[src] = true;
            topo.clear();
            topo.push(src);
            sum.iter_mut().for_each(|s| *s = 0);
            loop {
                for i in 0.. {
                    if used[dst] || i >= topo.len() {
                        break;
                    }
                    let v = topo[i];
                    for &(u, c, _) in self.graph[v].iter() {
                        sum[u] += c;
                        if !used[u] && sum[u] >= f {
                            used[u] = true;
                            topo.push(u);
                        }
                    }
                }
                if !used[dst] {
                    break;
                }
                pass[dst] = f;
                for v in topo.drain(1..).rev() {
                    sum[v] = 0;
                    used[v] = false;
                    let mut c = pass[v];
                    pass[v] = 0;
                    let mut pos = 0;
                    while let Some(&(u, _, inv)) = self.graph[v].get(pos) {
                        sum[u] = 0;
                        if used[u] {
                            let capa = self.graph[u][inv].1.min(c);
                            c -= capa;
                            pass[u] += capa;
                            self.graph[u][inv].1 -= capa;
                            self.graph[v][pos].1 += capa;
                        }
                        pos += 1;
                    }
                }
            }
            f /= 2;
        }
        pass[src]
    }
}

fn read() -> (usize, usize, Vec<Vec<i64>>, Vec<i64>, Vec<i64>) {
    let mut s = String::new();
    use std::io::*;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let mut next = || it.next().unwrap().parse::<i64>().unwrap();
    let h = next() as usize;
    let w = next() as usize;
    let mut g = vec![vec![0i64; w]; h];
    let mut r = vec![0; h];
    let mut c = vec![0; w];
    for g in g.iter_mut().flatten().chain(&mut r).chain(&mut c) {
        *g = next();
    }
    (h, w, g, r, c)
}

fn run() {
    let (h, w, a, r, c) = read();
    let mut graph = Fujishige::new(h + w + 2);
    let src = h + w;
    let dst = src + 1;
    for (i, a) in a.iter().enumerate() {
        let mut local = 0;
        for (j, a) in a.iter().enumerate() {
            graph.add_edge(h + j, i, *a);
            local += *a;
        }
        graph.add_edge(i, dst, local);
    }
    let mut sum = 0;
    for (i, r) in r.iter().enumerate() {
        sum += *r;
        graph.add_edge(src, i, *r);
    }
    for (i, c) in c.iter().enumerate() {
        sum += *c;
        graph.add_edge(src, i + h, *c);
    }
    let ans = sum - graph.flow(src, dst);
    println!("{}", ans);
}

fn main() {
    run();
}
0