Maximum Flow in a Directed Network

You are given a directed graph with n vertices and m edges. Each edge has a given capacity. Your task is to compute the maximum flow from the source vertex s to the sink vertex t.

The problem can be formally defined as follows:

Given a graph \( G = (V, E) \) with \( |V| = n \) and \( |E| = m \), and for each edge \( (u,v) \in E \) a capacity \( c(u,v) \), determine the maximum flow from the source vertex \( s \) to the sink vertex \( t \) according to the flow conservation and capacity constraints.

Note: All formulas are in \( \LaTeX \) format.

The flow must satisfy the following conditions:

• Capacity Constraint: \( 0 \le f(u,v) \le c(u,v) \) for every \( (u,v) \in E \).
• Flow Conservation: For all vertices \( u \in V \setminus \{s,t\} \), \( \sum_{v: (u,v) \in E} f(u,v) = \sum_{v: (v,u) \in E} f(v,u) \).

inputFormat

The first line of input contains four integers: n, m, s, and t, representing the number of vertices, the number of edges, the source vertex, and the sink vertex respectively.

Each of the following m lines contains three integers: u, v, and c, indicating there is a directed edge from vertex u to vertex v with capacity c.

outputFormat

Output a single integer which is the maximum flow from vertex s to vertex t.

sample

4 5 1 4
1 2 40
1 3 20
2 3 10
2 4 20
3 4 30

40