Language: C++

/// `Property` trait is for properties of edges.
pub trait Property: Copy {}

impl<P> Property for P where P: Copy {}

pub trait ZeroP {
    fn zero() -> Self;
}

impl ZeroP for usize { fn zero() -> Self { 0 } }
impl ZeroP for u8 { fn zero() -> Self { 0 } }
impl ZeroP for u16 { fn zero() -> Self { 0 } }
impl ZeroP for u32 { fn zero() -> Self { 0 } }
impl ZeroP for u64 { fn zero() -> Self { 0 } }
impl ZeroP for isize { fn zero() -> Self { 0 } }
impl ZeroP for i8 { fn zero() -> Self { 0 } }
impl ZeroP for i16 { fn zero() -> Self { 0 } }
impl ZeroP for i32 { fn zero() -> Self { 0 } }
impl ZeroP for i64 { fn zero() -> Self { 0 } }

/// `Weighted` trait is for properties of edges such as distance,cost and so on.
pub trait Weighted: Property + std::ops::Add<Output=Self> + std::cmp::Ord + ZeroP {}

impl<W> Weighted for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord + ZeroP {}

/// `NonNegativeWeighted` trait is for algorithm such Dijkstra's Algorithm.
pub trait NonNegativeWeighted: Weighted {}

impl NonNegativeWeighted for usize {}

pub trait Capacity: Weighted + std::ops::Sub<Output=Self>{}

impl Capacity for usize {}

pub trait Cost: Capacity + std::ops::Mul<Output=Self> {}  
  
/// Vertex object for graphs. it has the index of the vertex.
#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Vertex(pub usize);
  
/// Edge object for graphs.
#[derive(Clone,Copy,Debug)]
pub struct Edge {
    /// index of the edge for edge property.
    pub index : usize,
    /// start vertex of the edge.
    pub from : Vertex,
    /// end vertex of the edge.
    pub to : Vertex
}
  
  
impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        self.index == other.index
    }
}
  
impl Eq for Edge {}
  
pub trait Graph<'a,VP: Property,EP: Property> {
    type EIter: std::iter::Iterator<Item=&'a Edge>;
      
    /// this method return the count of vertices of graph.
    fn vertices_cnt(&self) -> usize;
    /// this method return the count of edges of graph.
    fn edges_cnt(&self) -> usize;
    /// this method add new edge to graph.
    fn add_edge(&mut self , from : &Vertex , to : &Vertex , edge_prop : EP);
    /// this method return mutable reference of v's property.
    fn vprop_mut(&mut self, v : &Vertex) -> &mut VP;
    /// this method return reference of v's property.
    fn vprop(&self, v : &Vertex) -> &VP;
    /// this method return mutable reference of e's property.
    fn eprop_mut(&mut self, e : &Edge) -> &mut EP;
    /// this method return reference of e's property.
    fn eprop(&self, e : &Edge) -> &EP;
  
    fn delta(&'a self , v : &Vertex) -> Self::EIter;
}
  
pub trait StaticGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
    /// this method create new graph object.
    /// n ... count of vertices.
    /// vp_init ... initial property of vertices.
    fn new(n : usize , vp_init : VP) -> Self;
}
pub trait DynamicGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
    fn new() -> Self;
    fn add_vertex(&'a mut self, v: &Vertex,vp: VP) -> bool;
    fn erase_vertex(&'a mut self,v: &Vertex) -> bool;
    fn erase_edge(&'a mut self, e: &Edge) -> bool;
}
  
pub trait Directed<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
}
pub trait Undirected<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
}
  
pub trait Bipartite<'a,VP: Property,EP: Property>: Undirected<'a,VP,EP> {
    fn binew(left: usize, right: usize, vp_init: VP) -> Self;
    fn left_cnt(&self) -> usize;
    fn right_cnt(&self)-> usize; 
    fn left_vertices(&self) -> std::slice::Iter<Vertex>;
    fn right_vertices(&self) -> std::slice::Iter<Vertex>;
}
  
  
/// struct for Directed Graph.
pub struct DirectedGraph<VP: Property,EP: Property> {
    n : usize,
    m : usize,
    g : Vec<Vec<Edge>>,
    es : Vec<EP>,
    vs : Vec<VP>
}
  
impl<'a,VP : Property ,EP : Property> Graph<'a,VP,EP> for DirectedGraph<VP,EP> {
    type EIter = std::slice::Iter<'a,Edge>;
      
    fn add_edge(&mut self , from : &Vertex , to : &Vertex , edge_prop : EP) {
        self.g[from.0].push(Edge{index : self.m, from : from.clone() , to : to.clone()});
        self.es.push(edge_prop);
        self.m += 1;
    }
    fn vertices_cnt(&self) -> usize { self.n }
    fn edges_cnt(&self) -> usize { self.m }
    fn vprop_mut(&mut self, v : &Vertex) -> &mut VP {
        &mut self.vs[v.0]
    }
    fn vprop(&self, v : &Vertex) -> &VP {
        & self.vs[v.0]
    }
    fn eprop_mut(&mut self, e : &Edge) -> &mut EP {
        &mut self.es[e.index]
    }
    fn eprop(&self, e : &Edge) -> &EP {
        & self.es[e.index]
    }
  
    fn delta(&'a self , v : &Vertex) -> Self::EIter {
        self.g[v.0].iter()
    }
}
  
impl<'a,VP : Property ,EP : Property> StaticGraph<'a,VP,EP> for DirectedGraph<VP,EP> {
    fn new(n : usize , vp_init: VP) -> Self {
        DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Edge>::new(); n],
            es: Vec::<EP>::new(),
            vs: vec![vp_init; n]
        }
    }
}
  
impl<'a,VP: Property, EP: Property> Directed<'a,VP,EP> for DirectedGraph<VP,EP> {
}
  
pub struct Network<C: Capacity> {
    pub cap: Vec<C>,
    pub flow: Vec<C>,
    pub g: DirectedGraph<usize,Edge>,
    pub source: Vertex,
    pub shink: Vertex,
    pub zero: C,
    pub inf: C,
    pub max_flow: C
}
  
impl<C: Capacity> Network<C> {
    pub fn build<VP: Property, EP: Property, F>(gg: &DirectedGraph<VP,EP>,s: Vertex, t: Vertex ,zero: C, inf: C,cap_sel: F) -> Network<C>
    where F: Fn(&EP) -> C {
        let mut g = DirectedGraph::<usize,Edge>::new(gg.vertices_cnt(),0);
        let mut cap = Vec::<C>::new();
        let flow = vec![zero;gg.edges_cnt() * 2];
  
        for i in 0..gg.vertices_cnt() {
            for e in gg.delta(&Vertex(i)) {
                let m = g.edges_cnt();
                g.add_edge(&e.from, &e.to, Edge {from: e.to, to: e.from, index: m + 1});
                cap.push(cap_sel(gg.eprop(e)));
                g.add_edge(&e.to, &e.from, Edge {from: e.from, to: e.to, index: m});
                cap.push(zero);
            }
        }
  
        Network {
            cap: cap,
            flow: flow,
            g: g,
            source: s,
            shink: t,
            zero: zero,
            inf,
            max_flow: zero
        }
    }
}
 
use std::cmp::min;
use std::cmp::max;

pub fn fujishige(net: &mut Network<usize>) -> usize {
    let ref mut cap = &mut net.cap;
    let ref g = & net.g;
    let s = net.source;
    let t = net.shink;
    let n = net.g.vertices_cnt();

    let mut alpha = usize::zero();
    for v in 0..n {
        for e in g.delta(&Vertex(v)) {
            alpha = max(alpha, cap[e.index]);
        }
    }
    let mut ans = 0;
    while alpha > usize::zero() {
        let mut i = 0;
        let mut isidxed = vec![0;n];
        let mut b = vec![usize::zero();n];
        let mut x = Vec::<Vertex>::new();
        x.push(s);
        isidxed[s.0] += 1;
        let mut ok = true;
        while x[i] != t {
            isidxed[x[i].0] += 1;
            for e in g.delta(&x[i]) {
                if cap[e.index] > usize::zero() && isidxed[e.to.0] != 2 {
                    b[e.to.0] = b[e.to.0] + cap[e.index];
                    if isidxed[e.to.0] == 0 && b[e.to.0] >= alpha {
                        x.push(e.to);
                        isidxed[e.to.0] += 1;
                    }
                }
            }
            if x.len() == i + 1 {
                alpha >>= 1;
                ok = false;
                break;
            }
            i = i + 1;
        }
        if !ok { continue; }

        let mut beta = vec![usize::zero();n];
        beta[t.0] = alpha;
        while i > 0 {
            isidxed[x[i].0] = 0;
            for rev in g.delta(&x[i]) {
                let e = g.eprop(rev);
                if isidxed[e.from.0] != 2 { continue; }
                let del = min(cap[e.index], beta[x[i].0]);
                cap[e.index] = cap[e.index] - del;
                cap[g.eprop(&e).index] = cap[g.eprop(&e).index] + del;
                if e.from == s {
                    ans += del;
                }
                if e.to == s {
                    ans -= del;
                }
                beta[x[i].0] = beta[x[i].0] - del;
                beta[e.from.0] = beta[e.from.0] + del;
            }
            i = i - 1;
        }
    }

    ans
}

 
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n,m) = (v[0] , v[1]);
    let mut g = DirectedGraph::<usize,usize>::new(n,0);
  
    for _ in 0..m {
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let a:Vec<usize> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (x,y,w) = (a[0],a[1],a[2]);
        g.add_edge(&Vertex(x),&Vertex(y),w);
    }
  
    let mut net = Network::<usize>::build(&g,Vertex(0),Vertex(n - 1),0,1e9 as usize,|w| w.clone());
    println!("{}", fujishige(&mut net));



Compiler output:
a.cc:38:2: error: invalid preprocessing directive #[
   38 | #[derive(Clone,Copy,Eq,PartialEq,Debug)]
      |  ^
a.cc:42:2: error: invalid preprocessing directive #[
   42 | #[derive(Clone,Copy,Debug)]
      |  ^
a.cc:61:17: warning: missing terminating ' character
   61 | pub trait Graph<'a,VP: Property,EP: Property> {
      |                 ^
a.cc:61:17: error: missing terminating ' character
   61 | pub trait Graph<'a,VP: Property,EP: Property> {
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:62:43: warning: missing terminating ' character
   62 |     type EIter: std::iter::Iterator<Item=&'a Edge>;
      |                                           ^
a.cc:62:43: error: missing terminating ' character
   62 |     type EIter: std::iter::Iterator<Item=&'a Edge>;
      |                                           ^~~~~~~~~
a.cc:79:15: warning: missing terminating ' character
   79 |     fn delta(&'a self , v : &Vertex) -> Self::EIter;
      |               ^
a.cc:79:15: error: missing terminating ' character
   79 |     fn delta(&'a self , v : &Vertex) -> Self::EIter;
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:82:23: warning: multi-character literal with 37 characters exceeds 'int' size of 4 bytes
   82 | pub trait StaticGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:88:24: warning: multi-character literal with 37 characters exceeds 'int' size of 4 bytes
   88 | pub trait DynamicGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
      |                        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:90:20: warning: missing terminating ' character
   90 |     fn add_vertex(&'a mut self, v: &Vertex,vp: VP) -> bool;
      |                    ^
a.cc:90:20: error: missing terminating ' character
   90 |     fn add_vertex(&'a mut self, v: &Vertex,vp: VP) -> bool;
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:91:22: warning: missing terminating ' character
   91 |     fn erase_vertex(&'a mut self,v: &Vertex) -> bool;
      |                      ^
a.cc:91:22: error: missing terminating ' character
   91 |     fn erase_vertex(&'a mut self,v: &Vertex) -> bool;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:92:20: warning: missing terminating ' character
   92 |     fn erase_edge(&'a mut self, e: &Edge) -> bool;
      |                    ^
a.cc:92:20: error: missing terminating ' character
   92 |     fn erase_edge(&'a mut self, e: &Edge) -> bool;
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:95:20: warning: multi-character literal with 36 characters exceeds 'int' size of 4 bytes
   95 | pub trait Directed<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
      |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:97:22: warning: multi-character literal with 36 characters exceeds 'int' size of 4 bytes
   97 | pub trait Undirected<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:100:21: warning: multi-character literal with 41 characters exceeds 'int' size of 4 bytes
  100 | pub trait Bipartite<'a,VP: Property,EP: Property>: Undirected<'a,VP,EP> {
      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:118:6: warning: multi-character literal with 38 characters exceeds 'int' size of 4 bytes
  118 | impl<'a,VP : Property ,EP : Property> Graph<'a,VP,EP> for DirectedGraph<VP,EP> {
      |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:119:35: warning: missing terminating ' character
  119 |     type EIter = std::slice::Iter<'a,Edge>;
      |                                   ^
a.cc:119:35: error: missing terminating ' character
  119 |     type EIter = std::slice::Iter<'a,Edge>;
      |                                   ^~~~~~~~~
a.cc:141:15: warning: missing terminating ' character
  141 |     fn delta(&'a self , v : &Vertex) -> Self::EIter {
      |               ^
a.cc:141:15: error: missing terminating ' character
  141 |     fn delta(&'a self , v : &Vertex) -> Self::EIter {
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:146:6: warning: multi-character literal with 44 characters exceeds 'int' size of 4 bytes
  146 | impl<'a,VP : Property ,EP : Property> StaticGraph<'a,VP,EP> for DirectedGraph<VP,EP> {
      |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:158:6: warning: multi-character literal with 39 characters exceeds 'int' size of 4 bytes
  158 | impl<'a,VP: Property, EP: Property> Directed<'a,VP,EP> for DirectedGraph<VP,EP> {
      |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:179:18: error: too many decimal points in number
  179 |         for i in 0..gg.vertices_cnt() {
      |                  ^~~~~~~~~~~~~~~~~~
a.cc:213:14: error: too many decimal points in number
  213 |     for v in 0..n {
      |              ^~~~
a.cc:282:14: error: too many decimal points in number
  282 |     for _ in 0..m {
      |              ^~~~
a.cc:2:1: error: 'pub' does not name a type
    2 | pub trait Property: Copy {}
      | ^~~
a.cc:4:1: error: 'impl' does not name a type
    4 | impl<P> Property for P where P: Copy {}
      | ^~~~
a.cc:6:1: error: 'pub' does not name a type
    6 | pub trait ZeroP {
      | ^~~
a.cc:10:1: error: 'impl' does not name a type
   10 | impl ZeroP for usize { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:11:1: error: 'impl' does not name a type
   11 | impl ZeroP for u8 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:12:1: error: 'impl' does not name a type
   12 | impl ZeroP for u16 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:13:1: error: 'impl' does not name a type
   13 | impl ZeroP for u32 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:14:1: error: 'impl' does not name a type
   14 | impl ZeroP for u64 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:15:1: error: 'impl' does not name a type
   15 | impl ZeroP for isize { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:16:1: error: 'impl' does not name a type
   16 | impl ZeroP for i8 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:17:1: error: 'impl' does not name a type
   17 | impl ZeroP for i16 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:18:1: error: 'impl' does not name a type
   18 | impl ZeroP for i32 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:19:1: error: 'impl' does not name a type
   19 | impl ZeroP for i64 { fn zero() -> Self { 0 } }
      | ^~~~
a.cc:22:1: error: 'pub' does not name a type
   22 | pub trait Weighted: Property + std::ops::Add<Output=Self> + std::cmp::Ord + ZeroP {}
      | ^~~
a.cc:24:1: error: 'impl' does not name a type
   24 | impl<W> Weighted for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord + ZeroP {}
      | ^~~~
a.cc:27:1: error: 'pub' does not name a type
   27 | pub trait NonNegativeWeighted: Weighted {}
      | ^~~
a.cc:29:1: error: 'impl' does not name a type
   29 | impl NonNegativeWeighted for usize {}
      | ^~~~
a.cc:31:1: error: 'pub' does not name a type
   31 | pub trait Capacity: Weighted + std::ops::Sub<Output=Self>{}
      | ^~~
a.cc:33:1: error: 'impl' does not name a type
   33 | impl Capacity for usize {}
      | ^~~~
a.cc:35:1: error: 'pub' does not name a type
   35 | pub trait Cost: Capacity + std::ops::Mul<Output=Self> {}
      | ^~~
a.cc:39:1: error: 'pub' does not name a type
   39 | pub struct Vertex(pub usize);
      | ^~~
a.cc:43:1: error: 'pub' does not name a type
   43 | pub struct Edge {
      | ^~~
a.cc:53:1: error: 'impl' does not name a type
   53 | impl PartialEq for Edge {
      | ^~~~
a.cc:59:1: error: 'impl' does not name a type
   59 | impl Eq for Edge {}
      | ^~~~
a.cc:61:1: error: 'pub' does not name a type
   61 | pub trait Graph<'a,VP: Property,EP: Property> {
      | ^~~
a.cc:67:5: error: 'fn' does not name a type
   67 |     fn edges_cnt(&self) -> usize;
      |     ^~
a.cc:69:5: error: 'fn' does not name a type
   69 |     fn add_edge(&mut self , from : &Vertex , to : &Vertex , edge_prop : EP);
      |     ^~
a.cc:71:5: error: 'fn' does not name a type
   71 |     fn vprop_mut(&mut self, v : &Vertex) -> &mut VP;
      |     ^~
a.cc:73:5: error: 'fn' does not name a type
   73 |     fn vprop(&self, v : &Vertex) -> &VP;
      |     ^~
a.cc:75:5: error: 'fn' does not name a type
   75 |     fn eprop_mut(&mut self, e : &Edge) -> &mut EP;
      |     ^~
a.cc:77:5: error: 'fn' does not name a type
   77 |     fn eprop(&self, e : &Edge) -> &EP;
      |     ^~
a.cc:79:5: error: 'fn' does not name a type
   79 |     fn delta(&'a self , v : &Vertex) -> Self::EIter;
      |     ^~
a.cc:80:1: error: expected declaration before '}' token
   80 | }
      | ^
a.cc:82:1: error: 'pub' does not name a type
   82 | pub trait StaticGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
      | ^~~
a.cc:88:1: error: 'pub' does not name a type
   88 | pub trait DynamicGraph<'a,VP: Property, EP: Property>: Graph<'a,VP,EP> {
      | ^~~
a.cc:95:1: error: 'pub' does not name a type
   95 | pub trait Directed<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
      | ^~~
a.cc:97:1: error: 'pub' does not name a type
   97 | pub trait Undirected<'a,VP: Property,EP: Property>: Graph<'a,VP,EP>{
      | ^~~
a.cc:100:1: error: 'pub' does not name a type
  100 | pub trait Bipartite<'a,VP: Property,EP: Property>: Undirected<'a,VP,EP> {
      | ^~~
a.cc:110:1: error: 'pub' does not name a type
  110 | pub struct DirectedGraph<VP: Property,EP: Property> {
      | ^~~
a.cc:118:1: error: 'impl' does not name a type
  118 | impl<'a,VP : Property ,EP : Property> Graph<'a,VP,EP> for DirectedGraph<VP,EP> {
      | ^~~~
a.cc:144:1: error: expected declaration before '}' token
  144 | }
      | ^
a.cc:146:1: error: 'impl' does not name a type
  146 | impl<'a,VP : Property ,EP : Property> StaticGraph<'a,VP,EP> for DirectedGraph<VP,EP> {
      | ^~~~
a.cc:158:1: error: 'impl' does not name a type
  158 | impl<'a,VP: Property, EP: Property> Directed<'a,VP,EP> for DirectedGraph<VP,EP> {
      | ^~~~
a.cc:161:1: error: 'pub' does not name a type
  161 | pub struct Network<C: Capacity> {
      | ^~~
a.cc:172:1: error: 'impl' does not name a type
  172 | impl<C: Capacity> Network<C> {
      | ^~~~
a.c