#1175517 (Rust) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: ngtkana
• 提出日時: 2026-08-06 19:17:03
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 32 ms / 2,000 ms
• コード長: 3,877 bytes
• コンパイル時間: 9,273 ms
• コンパイル使用メモリ: 199,492 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-06 19:17:14
• 合計ジャッジ時間: 10,803 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

use itertools::Itertools;
use proconio::{input, marker::Usize1};
use std::{collections::VecDeque, iter::Peekable, slice::Iter};

fn main() {
    input! {
        n: usize,
        m: usize,
        d: u64,
        airplains: [(Usize1, Usize1, u64, u64, u64); m],
    }
    let mut counter = 0..;
    let nodes = vec_from_fn(2 * m, |_| counter.next().unwrap());
    let source = counter.next().unwrap();
    let sink = counter.next().unwrap();

    let mut events = vec![vec![]; n];
    let mut inst = MaxFlow::new();
    for (i, &(u, v, p, q, w)) in airplains.iter().enumerate() {
        events[u].push((2 * p + 1, nodes[2 * i]));
        events[v].push((2 * (q + d), nodes[2 * i + 1]));
        inst.add_edge(2 * i, 2 * i + 1, w);
    }
    for e in &mut events {
        e.sort_unstable();
        for ((_, x), (_, y)) in e.iter().copied().tuple_windows() {
            inst.add_edge(nodes[x], nodes[y], u64::MAX);
        }
    }
    if let Some(&(_, x)) = events[0].first() {
        inst.add_edge(source, x, u64::MAX);
    }
    if let Some(&(_, x)) = events[n - 1].last() {
        inst.add_edge(x, sink, u64::MAX);
    }
    let flow = inst.solve(counter.start, source, sink);

    println!("{flow}");
}

fn vec_from_fn<T>(len: usize, f: impl FnMut(usize) -> T) -> Vec<T> {
    (0..len).map(f).collect()
}

#[derive(Default)]
pub struct MaxFlow {
    edges: Vec<Edge>,
}

impl MaxFlow {
    pub fn new() -> Self {
        Self::default()
    }
    pub fn add_edge(&mut self, src: usize, tar: usize, cap: u64) {
        self.edges.push(Edge { src, tar, cap });
        self.edges.push(Edge {
            src: tar,
            tar: src,
            cap: 0,
        });
    }
    pub fn solve(&mut self, n: usize, source: usize, sink: usize) -> u64 {
        let mut result = 0;
        let mut g = vec![vec![]; n];
        for (i, e) in self.edges.iter().enumerate() {
            g[e.src].push(i);
        }
        loop {
            let mut level = vec![usize::MAX; n];
            bfs(source, &mut level, &g, &self.edges);
            if level[sink] == usize::MAX {
                return result;
            }
            let mut used = vec![false; n];
            let mut iter = g.iter().map(|g| g.iter().peekable()).collect::<Vec<_>>();
            while {
                let f = dfs(
                    u64::MAX,
                    source,
                    sink,
                    &mut used,
                    &mut level,
                    &mut iter,
                    &mut self.edges,
                );
                result += f;
                f != 0
            } {}
        }
    }
}

fn bfs(source: usize, level: &mut [usize], g: &[Vec<usize>], edges: &[Edge]) {
    let mut queue = VecDeque::from([source]);
    level[source] = 0;
    while let Some(x) = queue.pop_front() {
        for &i in &g[x] {
            let y = edges[i].tar;
            if edges[i].cap == 0 || level[y] != usize::MAX {
                continue;
            }
            queue.push_back(y);
            level[y] = level[x] + 1;
        }
    }
}

fn dfs(
    f: u64,
    x: usize,
    sink: usize,
    used: &mut [bool],
    level: &mut [usize],
    iter: &mut [Peekable<Iter<'_, usize>>],
    edges: &mut [Edge],
) -> u64 {
    if x == sink {
        return f;
    }
    used[x] = true;
    while let Some(&&i) = iter[x].peek() {
        let e = edges[i];
        let y = e.tar;
        if used[y] || e.cap == 0 || level[x] >= level[y] {
            iter[x].next().unwrap();
            continue;
        }
        let f = dfs(f.min(e.cap), y, sink, used, level, iter, edges);
        if f > 0 {
            edges[i].cap -= f;
            edges[i ^ 1].cap += f;
            return f;
        }
        iter[x].next().unwrap();
    }
    level[x] = usize::MAX;
    0
}

#[derive(Clone, Copy, Debug)]
struct Edge {
    src: usize,
    tar: usize,
    cap: u64,
}