実装上の注意点
- TLEに気をつける
- xを実数にすると計算誤差が怖いので、(N+1)倍して整数演算にする
提出: #4130939 (Rust)
/**
* 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<T> {
to: usize,
cap: T,
rev: usize,
}
struct Dinic<T> {
graph: Vec<Vec<Edge<T>>>,
iter: Vec<usize>,
zero: T,
}
impl<T> Dinic<T>
where T: Clone,
T: Copy,
T: Ord,
T: std::ops::AddAssign,
T: std::ops::SubAssign,
{
fn bfs(&self, s: usize, level: &mut [Option<usize>]) {
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);
}
}
}
}
fn dfs(&mut self, v: usize, t: usize, f: Option<T>, level: &mut [Option<usize>]) -> 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<usize>) {
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;
}
}
}
}
fn calc(n: usize, a: &[i64], b: &[i64], pairs: &[(usize, usize)], mid: i64)
-> (i64, i64) {
let bias = 5001;
let mut din = Dinic::new(2 + n, 0);
let ni = n as i64;
for i in 0 .. n {
din.add_edge(0, 2 + i, (ni - b[i]) * bias);
din.add_edge(2 + i, 1, (ni - a[i]) * bias);
let (u, v) = pairs[i];
din.add_edge(2 + u, 2 + v, mid);
}
let (_cost, t_side) = din.max_flow(0, 1);
let mut kind = vec![0; n];
for t in t_side {
if t >= 2 {
kind[t - 2] = 1;
}
}
let mut used = 0;
for i in 0 .. n {
let (u, v) = pairs[i];
if (kind[u], kind[v]) == (0, 1) { used += 1; }
}
let mut realcost = 0;
for i in 0 .. n {
if kind[i] == 1 {
realcost += b[i];
} else {
realcost += a[i];
}
}
(realcost, used)
}
fn solve() {
let out = std::io::stdout();
let mut out = BufWriter::new(out.lock());
macro_rules! puts {
($format:expr) => (write!(out,$format).unwrap());
($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
}
input! {
n: usize,
k: usize,
a: [i64; n],
b: [i64; n],
}
let mut fail = -1;
let mut pass: i64 = 5001 * 5001;
let mut pairs = vec![(0, 0); n];
for i in 0 .. n {
pairs[a[i] as usize - 1].0 = i;
pairs[b[i] as usize - 1].1 = i;
}
while pass - fail > 1 {
let mid = (pass + fail) / 2;
let (_cost, pair) = calc(n, &a, &b, &pairs, mid);
if pair <= (n - k) as i64 {
pass = mid;
} else {
fail = mid;
}
}
let (cost, _) = calc(n, &a, &b, &pairs, pass);
puts!("{}\n", cost);
}
