結果
問題 | No.1479 Matrix Eraser |
ユーザー |
![]() |
提出日時 | 2021-04-16 20:55:19 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 300 ms / 3,000 ms |
コード長 | 7,805 bytes |
コンパイル時間 | 16,247 ms |
コンパイル使用メモリ | 379,760 KB |
実行使用メモリ | 37,888 KB |
最終ジャッジ日時 | 2024-07-02 23:38:20 |
合計ジャッジ時間 | 23,182 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
// ---------- begin max flow (Dinic) ----------mod maxflow {pub trait MaxFlowCapacity:Copy + Ord + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self>{fn zero() -> Self;fn inf() -> Self;}macro_rules! impl_primitive_integer_capacity {($x:ty, $y:expr) => {impl MaxFlowCapacity for $x {fn zero() -> Self {0}fn inf() -> Self {$y}}};}impl_primitive_integer_capacity!(u32, std::u32::MAX);impl_primitive_integer_capacity!(u64, std::u64::MAX);impl_primitive_integer_capacity!(i32, std::i32::MAX);impl_primitive_integer_capacity!(i64, std::i64::MAX);impl_primitive_integer_capacity!(usize, std::usize::MAX);#[derive(Clone)]struct Edge<Cap> {to_: u32,inv_: u32,cap_: Cap,}impl<Cap> Edge<Cap> {fn new(to: usize, inv: usize, cap: Cap) -> Self {Edge {to_: to as u32,inv_: inv as u32,cap_: cap,}}fn to(&self) -> usize {self.to_ as usize}fn inv(&self) -> usize {self.inv_ as usize}}impl<Cap: MaxFlowCapacity> Edge<Cap> {fn add(&mut self, cap: Cap) {self.cap_ = self.cap_ + cap;}fn sub(&mut self, cap: Cap) {self.cap_ = self.cap_ - cap;}fn cap(&self) -> Cap {self.cap_}}pub struct Graph<Cap> {graph: Vec<Vec<Edge<Cap>>>,}#[allow(dead_code)]pub struct EdgeIndex {src: usize,dst: usize,x: usize,y: usize,}impl<Cap: MaxFlowCapacity> Graph<Cap> {pub fn new(size: usize) -> Self {Self {graph: vec![vec![]; size],}}pub fn add_edge(&mut self, src: usize, dst: usize, cap: Cap) -> EdgeIndex {assert!(src.max(dst) < self.graph.len());assert!(cap >= Cap::zero());assert!(src != dst);let x = self.graph[src].len();let y = self.graph[dst].len();self.graph[src].push(Edge::new(dst, y, cap));self.graph[dst].push(Edge::new(src, x, Cap::zero()));EdgeIndex { src, dst, x, y }}// src, dst, used, intial_capacity#[allow(dead_code)]pub fn get_edge(&self, e: &EdgeIndex) -> (usize, usize, Cap, Cap) {let max = self.graph[e.src][e.x].cap() + self.graph[e.dst][e.y].cap();let used = self.graph[e.dst][e.y].cap();(e.src, e.dst, used, max)}pub fn flow(&mut self, src: usize, dst: usize) -> Cap {let size = self.graph.len();assert!(src.max(dst) < size);assert!(src != dst);let mut queue = std::collections::VecDeque::new();let mut level = vec![0; size];let mut it = vec![0; size];let mut ans = Cap::zero();loop {(|| {level.clear();level.resize(size, 0);level[src] = 1;queue.clear();queue.push_back(src);while let Some(v) = queue.pop_front() {let d = level[v] + 1;for e in self.graph[v].iter() {let u = e.to();if e.cap() > Cap::zero() && level[u] == 0 {level[u] = d;if u == dst {return;}queue.push_back(u);}}}})();if level[dst] == 0 {break;}it.clear();it.resize(size, 0);loop {let f = self.dfs(dst, src, Cap::inf(), &mut it, &level);if f == Cap::zero() {break;}ans = ans + f;}}ans}fn dfs(&mut self, v: usize, src: usize, cap: Cap, it: &mut [usize], level: &[u32]) -> Cap {if v == src {return cap;}while let Some((u, inv)) = self.graph[v].get(it[v]).map(|p| (p.to(), p.inv())) {if level[u] + 1 == level[v] && self.graph[u][inv].cap() > Cap::zero() {let cap = cap.min(self.graph[u][inv].cap());let c = self.dfs(u, src, cap, it, level);if c > Cap::zero() {self.graph[v][it[v]].add(c);self.graph[u][inv].sub(c);return c;}}it[v] += 1;}Cap::zero()}}}// ---------- end max flow (Dinic) ----------// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------fn run() {input! {h: usize,w: usize,a: [[u32; w]; h],}let mut map = std::collections::BTreeMap::new();for (i, a) in a.iter().enumerate() {for (j, a) in a.iter().enumerate() {if *a > 0 {map.entry(*a).or_insert(vec![]).push((i, j));}}}let mut ans = 0;for (_, a) in map.iter().rev() {let mut v = vec![];for &(x, y) in a.iter() {v.push(x);v.push(y + h);}v.sort();v.dedup();let mut g = maxflow::Graph::new(v.len() + 2);let src = v.len();let dst = src + 1;for (i, v) in v.iter().enumerate() {if *v < h {g.add_edge(src, i, 1);} else {g.add_edge(i, dst, 1);}}for &(x, y) in a.iter() {let x = v.binary_search(&x).unwrap();let y = v.binary_search(&(y + h)).unwrap();g.add_edge(x, y, 1);}ans += g.flow(src, dst);}println!("{}", ans);}fn main() {run();}