結果

問題 No.1479 Matrix Eraser
ユーザー akakimidori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// ---------- 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/0ba42c7ca36cd29d0ac8
macro_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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0