結果
| 問題 |
No.957 植林
|
| ユーザー |
 akakimidori
|
| 提出日時 | 2021-11-24 14:47:24 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 737 ms / 2,000 ms |
| コード長 | 6,341 bytes |
| コンパイル時間 | 13,520 ms |
| コンパイル使用メモリ | 403,860 KB |
| 実行使用メモリ | 10,828 KB |
| 最終ジャッジ日時 | 2024-06-27 00:05:40 |
| 合計ジャッジ時間 | 31,319 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
ソースコード
// ---------- 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);
#[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) ----------
fn read() -> (usize, usize, Vec<Vec<i64>>, Vec<i64>, Vec<i64>) {
let mut s = String::new();
use std::io::Read;
std::io::stdin().read_to_string(&mut s).unwrap();
let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<i64>());
let mut next = || it.next().unwrap();
let h = next() as usize;
let w = next() as usize;
let mut g = vec![vec![0; w]; h];
let mut r = vec![0; h];
let mut c = vec![0; w];
for a in g.iter_mut().flatten().chain(&mut r).chain(&mut c) {
*a = next();
}
(h, w, g, r, c)
}
fn main() {
let (h, w, g, r, c) = read();
let mut graph = maxflow::Graph::new(h + w + 2);
let src = h + w;
let dst = src + 1;
for (i, r) in r.iter().enumerate() {
graph.add_edge(src, i, *r);
}
for (j, c) in c.iter().enumerate() {
graph.add_edge(src, h + j, *c);
}
for (i, g) in g.iter().enumerate() {
for (j, g) in g.iter().enumerate() {
graph.add_edge(i, dst, *g);
graph.add_edge(h + j, i, *g);
}
}
let ans = r.iter().chain(&c).sum::<i64>() - graph.flow(src, dst);
println!("{}", ans);
}