FFLOW - Fast Maximum Flow

Given a graph with N (2 ≤ N ≤ 5,000) vertices numbered 1 to N and M (1 ≤ M ≤ 30,000) undirected, weighted edges, compute the maximum flow / minimum cut from vertex 1 to vertex N.

Input

The first line contains the two integers N and M. The next M lines each contain three integers A, B, and C, denoting that there is an edge of capacity C (1 ≤ C ≤ 109) between nodes A and B (1 ≤ A, B ≤ N). Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself.

Output

Print a single integer (which may not fit into a 32-bit integer) denoting the maximum flow / minimum cut between 1 and N.

Example

Input:
4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

Output:
5

Viewing the problem as max-flow, we may send 3 units of flow through the path 1 - 2 - 3 - 4 and 2 units of flow through the path 1 - 3 - 4. Viewing the problem as min-cut, we may cut the first and third edges. Either way the total is 5.

Original problem: https://www.spoj.com/problems/FASTFLOW/.


Được gửi lên bởi:Race with time
Ngày:2009-04-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Neal Wu - SPOJ

hide comments
2020-05-11 21:34:01
Why is pypy explicitly disallowed? I have a pypy solution I want to try out =/
2018-01-30 03:29:22 hồ vãn tuấn
sub ở đây thì qua mà bài gốc thì die
2017-12-19 01:52:51
sub bài gốc thì qua mà sub ở đây thì TLE :(
2016-07-05 14:33:08
http://code.vsj.com.vn/spoj-fflow/
2009-06-02 03:00:15 Lê Minh Hoàng
Bài này có thể vào dùng FIFO preflow-push hoặc Lift-to-front preflow-push kết hợp với gap-heuristic hoặc global heuristic mới chịu được. Gap-H trung bình chạy nhanh hơn nhưng có trường hợp xấu nên bị bộ test bắt được => sẽ bị TLE!

Last edit: 2010-06-29 02:01:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.