結果

問題 No.957 植林
ユーザー akakimidoriakakimidori
提出日時 2020-02-13 21:11:51
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 689 ms / 2,000 ms
コード長 8,380 bytes
コンパイル時間 21,527 ms
コンパイル使用メモリ 378,172 KB
実行使用メモリ 23,976 KB
最終ジャッジ日時 2024-10-06 06:24:26
合計ジャッジ時間 30,561 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 81 ms
19,144 KB
testcase_04 AC 73 ms
18,116 KB
testcase_05 AC 81 ms
19,688 KB
testcase_06 AC 85 ms
20,572 KB
testcase_07 AC 81 ms
18,592 KB
testcase_08 AC 61 ms
15,784 KB
testcase_09 AC 60 ms
15,800 KB
testcase_10 AC 68 ms
17,208 KB
testcase_11 AC 65 ms
16,552 KB
testcase_12 AC 62 ms
16,528 KB
testcase_13 AC 50 ms
13,056 KB
testcase_14 AC 67 ms
16,664 KB
testcase_15 AC 59 ms
15,024 KB
testcase_16 AC 53 ms
13,372 KB
testcase_17 AC 56 ms
14,416 KB
testcase_18 AC 512 ms
20,192 KB
testcase_19 AC 525 ms
20,840 KB
testcase_20 AC 545 ms
21,128 KB
testcase_21 AC 581 ms
21,596 KB
testcase_22 AC 589 ms
22,432 KB
testcase_23 AC 588 ms
23,144 KB
testcase_24 AC 639 ms
23,056 KB
testcase_25 AC 673 ms
23,456 KB
testcase_26 AC 662 ms
23,716 KB
testcase_27 AC 689 ms
23,640 KB
testcase_28 AC 634 ms
23,592 KB
testcase_29 AC 653 ms
23,976 KB
testcase_30 AC 644 ms
23,728 KB
testcase_31 AC 490 ms
20,220 KB
testcase_32 AC 514 ms
20,808 KB
testcase_33 AC 535 ms
21,088 KB
testcase_34 AC 566 ms
21,592 KB
testcase_35 AC 597 ms
22,440 KB
testcase_36 AC 605 ms
23,272 KB
testcase_37 AC 632 ms
23,052 KB
testcase_38 AC 651 ms
23,460 KB
testcase_39 AC 652 ms
23,840 KB
testcase_40 AC 635 ms
23,584 KB
testcase_41 AC 55 ms
12,972 KB
testcase_42 AC 56 ms
12,932 KB
testcase_43 AC 65 ms
16,056 KB
testcase_44 AC 73 ms
20,928 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://cp-algorithms.com/graph/mpm.html

use std::cmp::*;

type FlowType = i64;

struct MPMGraph {
    size: usize,
    edge: Vec<(usize, usize, FlowType)>,
}

impl MPMGraph {
    pub fn new(size: usize) -> Self {
        MPMGraph {
            size: size,
            edge: vec![],
        }
    }
    fn add_edge(&mut self, src: usize, dst: usize, capa: FlowType) {
        assert!(src < self.size && dst < self.size);
        if src != dst {
            self.edge.push((src, dst, capa));
            self.edge.push((dst, src, 0));
        }
    }
    #[inline(never)]
    fn flow(&mut self, src: usize, dst: usize) -> FlowType {
        // 多重辺のマージ
        self.edge.sort();
        self.edge.dedup_by(|a, b| {
            if a.0 == b.0 && a.1 == b.1 {
                b.2 += a.2;
                true
            } else {
                false
            }
        });
        // 逆辺への参照を取得
        let mut edge = Vec::with_capacity(self.edge.len());
        for &(s, t, c) in self.edge.iter() {
            let k = self.edge.binary_search_by(|e| (e.0, e.1).cmp(&(t, s))).unwrap();
            edge.push((s, t, c, k));
        }
        let mut graph = vec![vec![]; self.size];
        let mut inv_graph = vec![vec![]; self.size];
        let mut flow_graph = vec![vec![]; self.size];
        let mut inv_flow_graph = vec![vec![]; self.size];
        // フローが流れなくなるまでループ
        let mut ans = 0;
        loop {
            // 到達可能性を確かめる
            for &(s, t, c, _) in edge.iter() {
                if c > 0 {
                    graph[s].push(t);
                    inv_graph[t].push(s);
                }
            }
            let depth = MPMGraph::bfs(src, dst, &graph);
            // 到達不能
            if depth[dst] >= self.size {
                break;
            }
            let inv_depth = MPMGraph::bfs(dst, src, &inv_graph);
            // depth, inv_depthから使用される可能性のある辺のみからなるグラフを構築
            // pin, pout は流入、流出
            let mut pin = vec![0; self.size];
            let mut pout = vec![0; self.size];
            for (i, &(s, t, c, _)) in edge.iter().enumerate() {
                if c > 0 && depth[s] + 1 == depth[t] && inv_depth[t] + 1 == inv_depth[s] {
                    flow_graph[s].push((t, i));
                    pout[s] += c;
                    pin[t] += c;
                    inv_flow_graph[t].push((s, i));
                }
            }
            // src, dstは適当に初期化
            let inf = 1_000_000_000_000_000_000i64;
            pout[src] = inf;
            pin[src] = inf;
            pout[dst] = inf;
            pin[dst] = inf;
            // 採用されたか
            let mut alive = vec![true; self.size];
            alive[src] = false;
            alive[dst] = false;
            // どこまでみたかのアレ
            let mut it = vec![0; self.size];
            let mut inv_it = vec![0; self.size];
            let mut assign = vec![0; self.size];
            let mut q = std::collections::VecDeque::new();
            loop {
                // ポテンシャルが最小のものを検索
                let mut v = (pout[src], src);
                for (u, (pin, (pout, alive))) in pin.iter().zip(pout.iter().zip(alive.iter())).enumerate() {
                    let pot = min(*pin, *pout);
                    assert!(pot >= 0);
                    if *alive {
                        v = min(v, (pot, u));
                    }
                }
                // 存在しないならbreak
                if v.1 == src {
                    break;
                }
                alive[v.1] = false;
                if v.0 == 0 {
                    MPMGraph::remove_node(v.1, &flow_graph, &inv_flow_graph, &mut edge, &mut pin, &mut pout);
                    continue;
                }
                ans += v.0;
                MPMGraph::push(v.1, dst, v.0, &flow_graph, &mut edge, &mut it, &mut pin, &mut pout, &mut assign, &mut q);
                MPMGraph::push(v.1, src, v.0, &inv_flow_graph, &mut edge, &mut inv_it, &mut pout, &mut pin, &mut assign, &mut q);
                MPMGraph::remove_node(v.1, &flow_graph, &inv_flow_graph, &mut edge, &mut pin, &mut pout);
            }
            for g in graph.iter_mut().chain(inv_graph.iter_mut()) {
                g.clear();
            }
            for g in flow_graph.iter_mut().chain(inv_flow_graph.iter_mut()) {
                g.clear();
            }
        }
        ans
    }
    #[inline(never)]
    fn push(src: usize, dst: usize, flow: FlowType, graph: &[Vec<(usize, usize)>], edge: &mut [(usize, usize, FlowType, usize)], it: &mut [usize], pin: &mut [FlowType], pout: &mut [FlowType], assign: &mut [FlowType], q: &mut std::collections::VecDeque<usize>) {
        assign[src] = flow;
        q.push_back(src);
        while let Some(v) = q.pop_front() {
            assert!(assign[v] > 0);
            assert!(pout[v] >= assign[v]);
            if v == dst {
                break;
            }
            let mut f = assign[v];
            for &(u, k) in graph[v][it[v]..].iter() {
                let capa = min(edge[k].2, min(pout[u], pin[u]));
                if capa > 0 && assign[u] == 0 {
                    q.push_back(u);
                }
                if capa >= f {
                    edge[k].2 -= f;
                    edge[edge[k].3].2 += f;
                    pout[v] -= f;
                    pin[u] -= f;
                    assign[u] += f;
                    f = 0;
                    break;
                }
                edge[k].2 -= capa;
                edge[edge[k].3].2 += capa;
                pout[v] -= capa;
                pin[u] -= capa;
                assign[u] += capa;
                f -= capa;
                it[v] += 1;
            }
            assign[v] = 0;
            assert!(f == 0);
        }
    }
    #[inline(never)]
    fn remove_node(v: usize, graph: &[Vec<(usize, usize)>], inv_graph: &[Vec<(usize, usize)>], edge: &mut [(usize, usize, FlowType, usize)], pin: &mut [FlowType], pout: &mut [FlowType]) {
        for &(u, k) in graph[v].iter() {
            let capa = min(edge[k].2, min(pin[u], pout[v]));
            pin[u] -= capa;
            pout[v] -= capa;
        }
        for &(u, k) in inv_graph[v].iter() {
            let capa = min(edge[k].2, min(pout[u], pin[v]));
            pout[u] -= capa;
            pin[v] -= capa;
        }
    }
    #[inline(never)]
    fn bfs(src: usize, dst: usize, graph: &[Vec<usize>]) -> Vec<usize> {
        let mut depth = vec![graph.len(); graph.len()];
        depth[src] = 0;
        let mut q = std::collections::VecDeque::new();
        q.push_back(src);
        'outer: while let Some(v) = q.pop_front() {
            for &u in graph[v].iter() {
                if depth[u] > depth[v] + 1 {
                    depth[u] = depth[v] + 1;
                    if u == dst {
                        break 'outer;
                    }
                    q.push_back(u);
                }
            }
        }
        depth
    }
}

fn run() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let h: usize = it.next().unwrap().parse().unwrap();
    let w: usize = it.next().unwrap().parse().unwrap();
    let a: Vec<Vec<i64>> = (0..h).map(|_| (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect()).collect();
    let r: Vec<i64> = (0..h).map(|_| it.next().unwrap().parse().unwrap()).collect();
    let c: Vec<i64> = (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect();
    let mut graph = MPMGraph::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