#[allow(unused_imports)] use std::cmp::*; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); read_value!($next, [$t; len]) }}; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } /** * Dinic's algorithm for maximum flow problem. * Verified by: yukicoder No.177 (http://yukicoder.me/submissions/148371) * Min-cut (the second element of max_flow's returned values) is not verified. */ #[derive(Clone)] struct Edge { to: usize, cap: T, rev: usize, // rev is the position of the reverse edge in graph[to] } struct Dinic { graph: Vec>>, iter: Vec, zero: T, } impl Dinic where T: Clone, T: Copy, T: Ord, T: std::ops::AddAssign, T: std::ops::SubAssign, { fn bfs(&self, s: usize, level: &mut [Option]) { let n = level.len(); for i in 0 .. n { level[i] = None; } let mut que = std::collections::VecDeque::new(); level[s] = Some(0); que.push_back(s); while let Some(v) = que.pop_front() { for e in self.graph[v].iter() { if e.cap > self.zero && level[e.to] == None { level[e.to] = Some(level[v].unwrap() + 1); que.push_back(e.to); } } } } /* search augment path by dfs. * if f == None, f is treated as infinity. */ fn dfs(&mut self, v: usize, t: usize, f: Option, level: &mut [Option]) -> T { if v == t { return f.unwrap(); } while self.iter[v] < self.graph[v].len() { let i = self.iter[v]; let e = self.graph[v][i].clone(); if e.cap > self.zero && level[v] < level[e.to] { let newf = std::cmp::min(f.unwrap_or(e.cap), e.cap); let d = self.dfs(e.to, t, Some(newf), level); if d > self.zero { self.graph[v][i].cap -= d; self.graph[e.to][e.rev].cap += d; return d; } } self.iter[v] += 1; } self.zero } pub fn new(n: usize, zero: T) -> Self { Dinic { graph: vec![Vec::new(); n], iter: vec![0; n], zero: zero, } } pub fn add_edge(&mut self, from: usize, to: usize, cap: T) { let added_from = Edge { to: to, cap: cap, rev: self.graph[to].len() }; let added_to = Edge { to: from, cap: self.zero, rev: self.graph[from].len() }; self.graph[from].push(added_from); self.graph[to].push(added_to); } pub fn max_flow(&mut self, s: usize, t: usize) -> (T, Vec) { let mut flow = self.zero; let n = self.graph.len(); let mut level = vec![None; n]; loop { self.bfs(s, &mut level); if level[t] == None { let ret = (0 .. n).filter(|&i| level[i] == None) .collect(); return (flow, ret); } self.iter.clear(); self.iter.resize(n, 0); loop { let f = self.dfs(s, t, None, &mut level); if f <= self.zero { break; } flow += f; } } } } trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); } impl Change for T { fn chmax(&mut self, x: T) { if *self < x { *self = x; } } fn chmin(&mut self, x: T) { if *self > x { *self = x; } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); } fn solve() { input! { n: usize, m: usize, d: i64, uvpqw: [(usize1, usize1, i64, i64, i64); m], } let mut ev = vec![vec![]; n]; for &(u, v, p, q, _) in &uvpqw { ev[u].push(p); ev[v].push(q + d); } for i in 0..n { ev[i].sort(); ev[i].dedup(); } let mut offset = vec![0; n + 1]; for i in 0..n { offset[i + 1] = offset[i] + ev[i].len(); } const INF: i64 = 1 << 60; let mut din = Dinic::new(offset[n], 0i64); for i in 0..n { if ev[i].is_empty() { continue; } for j in 0..ev[i].len() - 1 { din.add_edge(offset[i] + j, offset[i] + j + 1, INF); } } for &(u, v, p, q, w) in &uvpqw { let l = ev[u].binary_search(&p).unwrap(); let r = ev[v].binary_search(&(q + d)).unwrap(); din.add_edge(offset[u] + l, offset[v] + r, w); } println!("{}", din.max_flow(0, offset[n] - 1).0); }