Download Speed

warning: unused imports: `Reverse`, `max`, `min`
 --> input/code.rs:1:16
  |
1 | use std::cmp::{max, min, Reverse};
  |                ^^^  ^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BTreeMap`, `BinaryHeap`, `HashMap`, `HashSet`
 --> input/code.rs:2:24
  |
2 | use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};
  |                        ^^^^^^^^  ^^^^^^^^^^  ^^^^^^^  ^^^^^^^

warning: unused import: `std::process::exit`
 --> input/code.rs:4:5
  |
4 | use std::process::exit;
  |     ^^^^^^^^^^^^^^^^^^

warning: 3 warnings emitted

use std::cmp::{max, min, Reverse};
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};
use std::io::{self, Read};
use std::process::exit;

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    // classes::c15::task2();
    homework::hw6::task2();
    // println!("{}", "-".repeat(20));
}
// */


fn main() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, m): (usize, usize) = (input!(it), input!(it));

    let mut capacity = vec![vec![0i64; n + 1]; n + 1];

    for _ in 0..m {
        let (a, b, c): (usize, usize, i64) = (input!(it), input!(it), input!(it));
        capacity[a][b] += c; 
    }

    let max_flow = ford_fulkerson(&mut capacity, 1, n);

    println!("{}", max_flow);
}

fn ford_fulkerson(capacity: &mut Vec<Vec<i64>>, source: usize, sink: usize) -> i64 {
    let n = capacity.len();
    let mut flow = 0;

    loop {
        let parent = bfs(capacity, source, sink, n);

        if parent[sink] == usize::MAX {  break; }

        let mut path_flow = i64::MAX;
        let mut v = sink;
        while v != source {
            let u = parent[v];
            path_flow = path_flow.min(capacity[u][v]);
            v = u;
        }

        v = sink;
        while v != source {
            let u = parent[v];
            capacity[u][v] -= path_flow;
            capacity[v][u] += path_flow;
            v = u;
        }

        flow += path_flow;
    }

    flow
}

fn bfs(capacity: &Vec<Vec<i64>>, source: usize, sink: usize, n: usize) -> Vec<usize> {
    let mut visited = vec![false; n];
    let mut parent = vec![usize::MAX; n];
    let mut queue = VecDeque::new();

    queue.push_back(source);
    visited[source] = true;

    while let Some(u) = queue.pop_front() {
        if u == sink {
            break;
        }

        for v in 1..n {
            if !visited[v] && capacity[u][v] > 0 {
                visited[v] = true;
                parent[v] = u;
                queue.push_back(v);
            }
        }
    }
    parent
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED