結果
問題 | No.957 植林 |
ユーザー | akakimidori |
提出日時 | 2020-02-13 22:56:39 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 5,051 bytes |
コンパイル時間 | 5,353 ms |
コンパイル使用メモリ | 159,620 KB |
実行使用メモリ | 13,268 KB |
最終ジャッジ日時 | 2024-04-15 23:30:03 |
合計ジャッジ時間 | 14,291 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 41 ms
10,048 KB |
testcase_04 | AC | 38 ms
9,536 KB |
testcase_05 | AC | 42 ms
10,208 KB |
testcase_06 | AC | 46 ms
10,860 KB |
testcase_07 | AC | 41 ms
9,760 KB |
testcase_08 | AC | 36 ms
10,280 KB |
testcase_09 | AC | 36 ms
10,428 KB |
testcase_10 | AC | 38 ms
10,900 KB |
testcase_11 | AC | 38 ms
10,276 KB |
testcase_12 | AC | 35 ms
10,256 KB |
testcase_13 | AC | 29 ms
9,360 KB |
testcase_14 | AC | 41 ms
11,292 KB |
testcase_15 | AC | 36 ms
12,016 KB |
testcase_16 | AC | 32 ms
9,396 KB |
testcase_17 | AC | 34 ms
9,556 KB |
testcase_18 | AC | 267 ms
10,088 KB |
testcase_19 | AC | 279 ms
10,316 KB |
testcase_20 | AC | 285 ms
10,568 KB |
testcase_21 | AC | 306 ms
10,708 KB |
testcase_22 | AC | 318 ms
11,100 KB |
testcase_23 | AC | 329 ms
13,072 KB |
testcase_24 | AC | 336 ms
11,672 KB |
testcase_25 | AC | 361 ms
11,804 KB |
testcase_26 | AC | 365 ms
12,992 KB |
testcase_27 | AC | 362 ms
13,268 KB |
testcase_28 | AC | 360 ms
11,940 KB |
testcase_29 | AC | 359 ms
11,940 KB |
testcase_30 | AC | 360 ms
11,936 KB |
testcase_31 | AC | 266 ms
11,800 KB |
testcase_32 | AC | 286 ms
10,316 KB |
testcase_33 | AC | 286 ms
10,568 KB |
testcase_34 | AC | 302 ms
12,392 KB |
testcase_35 | AC | 318 ms
11,100 KB |
testcase_36 | AC | 331 ms
12,884 KB |
testcase_37 | AC | 337 ms
11,536 KB |
testcase_38 | AC | 364 ms
12,768 KB |
testcase_39 | AC | 365 ms
11,940 KB |
testcase_40 | AC | 367 ms
11,936 KB |
testcase_41 | AC | 41 ms
11,560 KB |
testcase_42 | AC | 42 ms
12,484 KB |
testcase_43 | AC | 44 ms
13,244 KB |
testcase_44 | AC | 46 ms
12,224 KB |
testcase_45 | AC | 1 ms
6,940 KB |
testcase_46 | AC | 1 ms
6,944 KB |
testcase_47 | AC | 1 ms
6,944 KB |
ソースコード
// 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(); }