Maximal Flows Dimension

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Consider an acyclic directed graph G each edge uv of which has some associated capacity c(uv). Let G
have two special vertices: source s and sink t.
A flow in G is the function f : E → R such that the following conditions are satisfied:
1. 0 ≤ f (uv) ≤ c(uv) for all edges uv.
2. for any vertex u except s and t 

      The value of the flow f denoted as |f | is the amount of flow coming out of the source:

      The flow is called maximal if |f | is maximal possible among all flows in G. 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 fmax A set of flows {f1,f2,..., fn} 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 αi ∈ R.
      The size of this set — n — is called the maximal flows dimension of the graph.
      Given graph G find its maximal flows dimension.

Input

      The first line of the input file contains n and m — the number of vertices and edges in the graph, respectively (1 ≤ n ≤ 10, 1 ≤ m ≤ 10). The following m 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 1, the sink has number n. Capacities do not exceed 104.
      It is guaranteed that there is a path from source to sink.

Output

      Output one number — the maximal flows dimension of the given graph.

Sample Input

2 1
1 2 1
4 5
1 2 2
1 3 2
3 2 1
2 4 2
3 4 1

Sample Output

0
1

Hint

戳我下载完整PDF

单组数据

Please distinguish the maximal flows dimension and the number of vertices, although both of two variable are instead of n, they are not the same.

Source

Andrew Stankevich Contest 22

Manager

Information
Solved Number3
Submit Number5
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel