コード
use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;
pub struct Edge {
pub to: usize,
pub rev: usize,
pub cap: i64,
}
struct Dinitz {
g: Vec<Vec<Edge>>,
level: Vec<i32>,
iter: Vec<usize>,
}
impl Dinitz {
fn new(v: usize) -> Dinitz {
let mut g: Vec<Vec<Edge>> = Vec::new();
for _ in 0..v {
g.push(Vec::new());
}
Dinitz {
g: g,
level: vec![0;v],
iter: vec![0;v],
}
}
fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
let to_len = self.g[to].len();
let from_len = self.g[from].len();
self.g[from].push(Edge {
to: to,
rev: to_len,
cap: cap,
});
self.g[to].push(Edge {
to: from,
rev: from_len,
cap: 0,
});
}
fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
if v == t {
return f;
}
while self.iter[v] < self.g[v].len() {
let (e_cap, e_to, e_rev);
{
let ref e = self.g[v][self.iter[v]];
e_cap = e.cap;
e_to = e.to;
e_rev = e.rev;
}
if e_cap > 0 && self.level[v] < self.level[e_to] {
let d = self.dfs(e_to, t, cmp::min(f, e_cap));
if d > 0 {
{
let ref mut e = self.g[v][self.iter[v]];
e.cap -= d;
}
{
let ref mut rev_edge = self.g[e_to][e_rev];
rev_edge.cap += d;
}
return d;
}
}
self.iter[v] += 1;
}
return 0;
}
fn bfs(&mut self, s: usize) {
let v = self.level.len();
self.level = vec![-1;v];
self.level[s] = 0;
let mut deque = VecDeque::new();
deque.push_back(s);
while !deque.is_empty() {
let v = deque.pop_front().unwrap();
for e in &self.g[v] {
if e.cap > 0 && self.level[e.to] < 0 {
self.level[e.to] = self.level[v] + 1;
deque.push_back(e.to);
}
}
}
}
fn max_flow(&mut self, s: usize, t: usize) -> i64 {
let v = self.level.len();
let mut flow: i64 = 0;
loop {
self.bfs(s);
if self.level[t] < 0 {
return flow;
}
self.iter = vec![0;v];
loop {
let f = self.dfs(s, t, MAX);
if f == 0 {
break;
}
flow += f;
}
}
}
}
fn main() {
let mut sc = Scanner::new();
let n = sc.parse::<usize>();
let g = sc.parse::<usize>();
let e = sc.parse::<usize>();
let v = n + 1;
let mut dinitz = Dinitz::new(v);
for _ in 0..g {
let p = sc.parse::<usize>();
dinitz.add_edge(p, n, 1);
}
for _ in 0..e {
let a = sc.parse::<usize>();
let b = sc.parse::<usize>();
dinitz.add_edge(a, b, 1);
dinitz.add_edge(b, a, 1);
}
let ans = dinitz.max_flow(0, n);
println!("{}", ans);
}
struct Scanner {
stdin: Stdin,
buf: Vec<u8>,
}
impl Scanner {
fn new() -> Scanner {
Scanner {
stdin: io::stdin(),
buf: Vec::with_capacity(256),
}
}
fn parse<T: FromStr>(&mut self) -> T
where <T as FromStr>::Err: Debug
{
self.buf.clear();
let mut it = self.stdin.lock().bytes();
let mut c = it.next().unwrap().unwrap();
while c == ' ' as u8 || c == '\n' as u8 {
c = it.next().unwrap().unwrap();
}
while !(c == ' ' as u8 || c == '\n' as u8) {
self.buf.push(c);
c = it.next().unwrap().unwrap();
}
str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
}
}