网络流模板题

最大流最小割

抽象成网络图。道路的起点和终点是网络的源汇点，每条边最多能通过的乌龟数是网络边的上界。问题就变成了求网络图的最小割。

由最大流最小割定理可得，最大流等于最小割，所以我们只需要跑一遍最大流就可以得到答案

fn solve(input: &mut FastReader<impl BufRead>, output: &mut BufWriter<impl Write>) -> Result<()> {
    let [n, m] = input.readln::<usize>()[..] else { todo!() };
    // 闭包函数用于快速计算点的坐标
    let at = |x: usize, y: usize| -> usize { (x - 1) * m + y - 1 };
    // 无费用的网络图。初始化点数和最大边数（防止动态开点导致的分配错误）
    let mut graph = NetworkFlow::with_capacity(n * m, 3000000, false);
    // 接下来建图
    for x in 1..=n {
        for (y, &flow) in input.readln::<i32>().iter().enumerate() {
            let y = y + 1;
            let (from, to) = (at(x, y), at(x, y + 1));
            graph.connect(from, to, flow);
            graph.connect(to, from, flow);
        }
    }
    for x in 1..n {
        for (y, &flow) in input.readln::<i32>().iter().enumerate() {
            let y = y + 1;
            let (from, to) = (at(x, y), at(x + 1, y));
            graph.connect(from, to, flow);
            graph.connect(to, from, flow);
        }
    }
    for x in 1..n {
        for (y, &flow) in input.readln::<i32>().iter().enumerate() {
            let y = y + 1;
            let (from, to) = (at(x, y), at(x + 1, y + 1));
            graph.connect(from, to, flow);
            graph.connect(to, from, flow);
        }
    }
    let (s, t) = (at(1, 1), at(n, m)); // 显然这两个点是源汇点
    let minimum_cut = graph.maximum_flow(s, t);    // 最大流最小割定理
    writeln!(output, "{}", minimum_cut)?;
    Ok(())
}