// 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)); } } 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 ans = 0; loop { // 到達可能性を確かめる let mut graph = vec![vec![]; self.size]; let mut inv_graph = vec![vec![]; self.size]; 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 flow_graph = vec![vec![]; self.size]; let mut inv_flow_graph = vec![vec![]; self.size]; 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; // siyousaretaka 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]; 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); if *alive && pot < v.0 { 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); MPMGraph::push(v.1, src, v.0, &inv_flow_graph, &mut edge, &mut inv_it, &mut pout, &mut pin); MPMGraph::remove_node(v.1, &flow_graph, &inv_flow_graph, &mut edge, &mut pin, &mut pout); } } ans } 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]) { let mut q = std::collections::VecDeque::new(); let mut assign = vec![0; graph.len()]; assign[src] = flow; q.push_back(src); while let Some(v) = q.pop_front() { 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(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; } assert!(f == 0); } assert!(assign[dst] == flow); } 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 = edge[k].2; pin[u] -= capa; } for &(u, k) in inv_graph[v].iter() { let capa = edge[k].2; pout[u] -= capa; } } fn bfs(src: usize, dst: usize, graph: &[Vec]) -> Vec { 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> = (0..h).map(|_| (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect()).collect(); let r: Vec = (0..h).map(|_| it.next().unwrap().parse().unwrap()).collect(); let c: Vec = (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(); }