Maximal Flows Dimension#8484
Consider an acyclic directed graph each edge of which has some associated capacity . Let have two special vertices: source and sink .
A flow in is the function f : E \to R such that the following conditions are satisfied:
0 \le f(uv) \le c(uv) for all edges .
for any vertex except and
The value of the flow denoted as is the amount of flow coming out of the source:
The flow is called maximal if is maximal possible among all flows in . Clearly there can be several maximal flows.
Flows can be added pointwise or multiplied by a real constant as any other functions. Let us fix some maximal flow f_{max}. A set of flows \{f_1, f_2, \ldots, f_n\} is said to form a basis of maximal flows if each maximal flow can be represented as the sum
and no its proper subset has this property. Here a_i belongs to .
The size of this set - - is called the maximal flows dimension of the graph.
Given graph find its maximal flows dimension.
The first line contains and - the number of vertices and edges in the graph, respectively (1 \le n \le 10, 1 \le m \le 10). The following lines contain three integer numbers each and describe edges. Each edge is described by the vertex it leaves, the vertex it enters, and its capacity. The given graph is acyclic. The source has number , the sink has number . Capacities do not exceed 10^4. It is guaranteed that there is a path from source to sink.
Output one number - the maximal flows dimension of the given graph.
Example 1
Example 2