find-the-flow

Given a directed flow network where each edge has a capacity of flow it could allow, find the maximum flow over the network from source(S) to sink(T).

Network will follow these rules:
Only one source(S) and only one sink(T).
Other than source and sink, nodes are represented with alphabets [A-O].
There are no self loops.
There will be no initial dead ends other than T.
For any pair of nodes, direction of edges between them will be in single direction.

Input Format:
First line has an integer E- number of edges.
Next E lines have three values V_i\;V_j\;C_x which implies there is a node from V_i to V_j with capacity C_x.

Output Format:
Print a single integer which is the maximum flow from source to sink.

Constraints:
1 ≤ E ≤ 50
1 ≤ C_x ≤ 50
Network includes S, T, a maximum of 15 other nodes.

SAMPLE INPUT
10
S A 8
S B 10
A B 4
A C 8
A D 5
B D 2
B C 5
C T 4
C D 3
D T 12

SAMPLE OUTPUT
14

Source: hackerearth | Difficulty: EASY
Tags: Flows and cuts


Solutions: