Download Speed

#![allow(unused)]

use std::io;

fn take_tuple() -> (usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap())
}

fn take_triple() -> (usize, usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap(), it.next().unwrap())
}

fn dfs(u: usize, min: usize, adj: &mut Vec<Vec<(usize, usize, usize)>>,
    visited: &mut Vec<bool>, thr: usize, sink: usize,) -> usize {
    if u == sink { return min; }
    visited[u] = true;

    for i in 0..adj[u].len() {
        let (v, c, rev) = adj[u][i];
        if c < thr || visited[v] { continue; }

        let f = dfs(v, min.min(c), adj, visited, thr, sink);
        if f > 0 {
            adj[u][i].1 -= f;
            adj[v][rev].1 += f;
            return f;
        }
    }
    0
}

fn main() {
    let (n, m): (usize, usize) = take_tuple();
    let mut adj: Vec<Vec<(usize, usize, usize)>> = vec![Vec::new(); n + 1];

    let mut flow_sum = 0;
    for i in 0..m {
        let (a, b, c) = take_triple();
        let rev_a = adj[b].len();
        let rev_b = adj[a].len();

        adj[a].push((b, c, rev_a));
        adj[b].push((a, 0, rev_b));
        flow_sum += c;
    }

    let mut thr: usize = flow_sum;
    flow_sum = 0;

    while thr > 0 {
        loop {
            let mut visited: Vec<bool> = vec![false; n + 1];
            let f = dfs(1, usize::MAX, &mut adj, &mut visited, thr, n);
            if f == 0 { break; }
            flow_sum += f;
        }
        thr = thr / 2;
    }

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

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