FFLOW - Fast Maximum Flow

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/fflow


Cho một đồ thị với N (2 ≤ N ≤ 5,000) đỉnh được đánh số từ 1 đến N và M (1 ≤ M ≤ 30,000) cạnh vô hướng, có trọng số, hãy tính giá trị của luồng cực đại / lát cắt cực tiểu từ đỉnh 1 đến đỉnh N

Input

Dòng đầu chứa hai số nguyên N và M. M dòng tiếp theo, mỗi dòng chứa ba số nguyên A, B, và C, thể hiện việc có một cạnh với khả năng thông qua C (1 ≤ C ≤ 109) giữa nút A và nút B (1 ≤ A, B ≤ N). Lưu ý rằng có thể có nhiều cạnh giữa hai nút, cũng như có thể có một cạnh từ một nút đến chính nó.

Output

Viết ra một số nguyên duy nhất (có thể vượt quá kiểu số nguyên 32 bit) thể hiện giá trị của luồng cực đại / lát cắt cực tiểu giữa 1 và 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

Nhìn bài toán dưới dạng luồng cực đại, ta có thể cho 3 đơn vị luồng chảy qua đường 1 - 2 - 3 - 4 và 2 đơn vị luồng qua đường 1 - 3 - 4. Nhìn dưới góc độ lát cắt cực tiểu, ta có thể cắt cạnh thứ nhất và thứ 3. Cả 2 cách đều có tổng giá trị là 5.

Bài gốc: 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.