Submission #2176519

---

Source Code Expand

use std::str::FromStr;
use std::io::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(&mut i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: &mut R, o: &mut W) {
    let mut i = AtRead::from(i);
    let (n, g, e) = i.read3::<usize, usize, usize>();
    let p = i.read_vec(g);
    let mut links = Vec::new();
    for _ in 0..e {
        links.push(i.read2());
    }
    let mut sns = Sns::new(n, p, links);
    writeln!(o, "{}", solve(&mut sns)).unwrap();
}
fn solve(sns: &mut Sns) -> usize {
    sns.prepare();

    let mut result = 0;
    while sns.visit() {
        // TODO
        result += 1;
    }

    result
}
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Flow {
    Up,   // インデックスが増える方向
    Down, // インデックスが減る方向
    None,
}

#[derive(Debug, Clone)]
struct Sns {
    n: usize,                         // ユーザー数
    links: Vec<(usize, usize)>,       // フレンドリンク
    targets: Vec<usize>,              // ターゲットのリスト
    linkids: Vec<Vec<Option<usize>>>, // linkids[a][b] はa,b間のフレンドのリンクのインデックス
    visits: Vec<Option<usize>>,       // visits[n]はユーザーID n のフレンド探索元
    flows: Vec<Flow>,                 // リンクの使用状況
    q: Vec<usize>,                    // self.v 計算用バッファ
}

impl Sns {
    fn new(n: usize, targets: Vec<usize>, links: Vec<(usize, usize)>) -> Self {
        let n = n + 1;
        let links_len = links.len();
        Sns {
            n: n,
            links: links,
            targets: targets,
            linkids: vec![vec![None; n]; n],
            visits: vec![None; n],
            flows: vec![Flow::None; links_len],
            q: Vec::new(),
        }
    }
    fn prepare_linkids(&mut self) {
        for i0 in 0..self.n {
            for i1 in 0..self.n {
                self.linkids[i0][i1] = None;
            }
        }
        for i in 0..self.links.len() {
            let link = self.links[i];
            self.linkids[link.0][link.1] = Some(i);
            self.linkids[link.1][link.0] = Some(i);
        }
    }
    fn visit(&mut self) -> bool {
        let n = self.n;
        self.visits.clear();
        self.visits.resize(n, None);

        self.q.clear();
        self.q.push(0);
        self.visits[0] = Some(0);
        while let Some(i0) = self.q.pop() {
            for i1 in 1..n {
                if self.try_move(i0, i1) {
                    if i1 == n - 1 {
                        self.apply_flow();
                        return true;
                    }
                    self.q.push(i1);
                }
            }
        }
        false
    }
    fn apply_flow(&mut self) {
        let mut to = self.n - 1;
        while to != 0 {
            let from = self.visits[to].unwrap();
            let l = self.linkids[from][to].unwrap();
            let flow = self.flows[l];
            self.flows[l] = if from < to {
                match flow {
                    Flow::Down => Flow::None,
                    Flow::None => Flow::Up,
                    _ => unreachable!(),
                }
            } else {
                match flow {
                    Flow::Up => Flow::None,
                    Flow::None => Flow::Down,
                    _ => unreachable!(),
                }
            };
            to = from;
        }
    }
    fn try_move(&mut self, from: usize, to: usize) -> bool {
        if self.visits[to].is_some() {
            return false;
        }
        if let Some(i) = self.linkids[from][to] {
            let flow = self.flows[i];
            if flow == Flow::Up && from < to {
                return false;
            }
            if flow == Flow::Down && from > to {
                return false;
            }
            self.visits[to] = Some(from);
            true
        } else {
            false
        }
    }
    fn prepare(&mut self) {
        self.prepare_linkids();
        self.visit();

        self.links = self.links
            .iter()
            .cloned()
            .filter(|i| self.visits[i.0].is_some())
            .collect();
        self.targets = self.targets
            .iter()
            .cloned()
            .filter(|&i| self.visits[i].is_some())
            .collect();

        let goal = self.n - 1;
        for &t in self.targets.iter() {
            self.links.push((t, goal));
        }
        self.prepare_linkids();
        self.flows.resize(self.links.len(), Flow::None);
    }
}

struct AtRead<'a, R: BufRead + 'a> {
    r: &'a mut R,
    s: String,
}

macro_rules! fn_read {
        {$f:ident($($v:ident: $t:ident),*)} => {
            fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.next().split(' ');
                $(
                    let $v = next(i);
                )*
                ($($v),*)
            }
        };
    }

impl<'a, R: BufRead + 'a> AtRead<'a, R> {
    fn from(r: &'a mut R) -> Self {
        AtRead {
            r: r,
            s: String::new(),
        }
    }
    fn next(&mut self) -> &str {
        self.s.clear();
        self.r.read_line(&mut self.s).unwrap();
        self.s.trim()
    }

    fn_read! { read2(v1: T1, v2: T2) }
    fn_read! { read3(v1: T1, v2: T2, v3: T3) }

    fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        self.next()
            .split(' ')
            .take(n)
            .map(|x| x.parse().ok().unwrap())
            .collect()
    }
}

fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
    i.next().unwrap().parse().ok().unwrap()
}

Submission Info

Judge Result