結果

問題 No.957 植林
ユーザー akakimidoriakakimidori
提出日時 2020-02-13 22:56:39
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 336 ms / 2,000 ms
コード長 5,051 bytes
コンパイル時間 22,966 ms
コンパイル使用メモリ 399,636 KB
実行使用メモリ 13,176 KB
最終ジャッジ日時 2024-10-06 06:40:07
合計ジャッジ時間 22,133 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 38 ms
10,176 KB
testcase_04 AC 34 ms
9,532 KB
testcase_05 AC 37 ms
10,208 KB
testcase_06 AC 41 ms
10,860 KB
testcase_07 AC 35 ms
9,588 KB
testcase_08 AC 32 ms
10,280 KB
testcase_09 AC 33 ms
10,168 KB
testcase_10 AC 34 ms
10,768 KB
testcase_11 AC 32 ms
10,284 KB
testcase_12 AC 30 ms
10,132 KB
testcase_13 AC 26 ms
9,360 KB
testcase_14 AC 37 ms
11,160 KB
testcase_15 AC 33 ms
10,068 KB
testcase_16 AC 29 ms
9,532 KB
testcase_17 AC 29 ms
9,640 KB
testcase_18 AC 252 ms
10,080 KB
testcase_19 AC 255 ms
10,440 KB
testcase_20 AC 257 ms
10,696 KB
testcase_21 AC 274 ms
10,840 KB
testcase_22 AC 296 ms
10,968 KB
testcase_23 AC 301 ms
13,156 KB
testcase_24 AC 313 ms
11,660 KB
testcase_25 AC 333 ms
11,812 KB
testcase_26 AC 330 ms
11,808 KB
testcase_27 AC 328 ms
11,812 KB
testcase_28 AC 328 ms
12,868 KB
testcase_29 AC 329 ms
11,940 KB
testcase_30 AC 330 ms
13,036 KB
testcase_31 AC 243 ms
10,216 KB
testcase_32 AC 256 ms
10,436 KB
testcase_33 AC 263 ms
10,696 KB
testcase_34 AC 299 ms
12,336 KB
testcase_35 AC 301 ms
10,972 KB
testcase_36 AC 309 ms
11,236 KB
testcase_37 AC 315 ms
11,536 KB
testcase_38 AC 334 ms
11,816 KB
testcase_39 AC 330 ms
11,940 KB
testcase_40 AC 336 ms
11,816 KB
testcase_41 AC 38 ms
11,432 KB
testcase_42 AC 37 ms
11,564 KB
testcase_43 AC 41 ms
12,096 KB
testcase_44 AC 40 ms
13,176 KB
testcase_45 AC 1 ms
6,816 KB
testcase_46 AC 0 ms
6,816 KB
testcase_47 AC 0 ms
6,816 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 deg = vec![0; self.size];
        for e in self.edge.iter() {
            deg[e.0] += 1;
        }
        let mut graph = Vec::with_capacity(self.size);
        for deg in deg.into_iter() {
            graph.push(Vec::with_capacity(deg));
        }
        // グラフの構築
        let mut used = vec![false; self.edge.len()];
        for (i, &(s, t, c)) in self.edge.iter().enumerate() {
            if used[i] {
                continue;
            }
            let x = graph[s].len();
            let y = graph[t].len();
            let k = self.edge.binary_search_by(|e| (e.0, e.1).cmp(&(t, s))).unwrap();
            graph[s].push((t, c, y));
            graph[t].push((s, self.edge[k].2, x));
            used[i] = true;
            used[k] = true;
        }
        // フローが流れなくなるまでループ
        let mut it = vec![0; self.size];
        let mut ans = 0;
        loop {
            // 到達可能性を確かめる
            let depth = MPMGraph::bfs(src, dst, &graph);
            // 到達不能
            if depth[dst] >= self.size {
                break;
            }
            it.clear();
            it.resize(self.size, 0);
            loop {
                let f = MPMGraph::dfs(dst, src, &mut graph, &mut it, 1_000_000_000_000_000_000i64, &depth);
                if f == 0 {
                    break;
                }
                ans += f;
            }
        }
        ans
    }
    #[inline(never)]
    fn dfs(v: usize, src: usize, graph: &mut [Vec<(usize, FlowType, usize)>], it: &mut [usize], mut capa: FlowType, depth: &[usize]) -> FlowType {
        if v == src {
            return capa;
        }
        let mut sum = 0;
        for i in it[v]..graph[v].len() {
            let (u, _, inv) = graph[v][i];
            if depth[u] < depth[v] && graph[u][inv].1 > 0 {
                let c = min(graph[u][inv].1, capa);
                let f = MPMGraph::dfs(u, src, graph, it, c, depth);
                sum += f;
                capa -= f;
                graph[v][i].1 += f;
                graph[u][inv].1 -= f;
                if capa == 0 {
                    return sum;
                }
            }
            it[v] += 1;
        }
        sum
    }
    #[inline(never)]
    fn bfs(src: usize, dst: usize, graph: &[Vec<(usize, FlowType, 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, c, _) in graph[v].iter() {
                if c > 0 && 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