結果

問題 No.957 植林
コンテスト
ユーザー akakimidori
提出日時 2021-10-07 23:28:23
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 3,845 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,653 ms
コンパイル使用メモリ 407,500 KB
実行使用メモリ 414,440 KB
最終ジャッジ日時 2024-07-23 03:10:12
合計ジャッジ時間 19,741 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 2 -- * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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