Fast Maximum Flow

View as PDF

Submit solution

Points: 1.67 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Neal Wu - SPOJ
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một đồ thị với ~N~ ~\left(2 \leq N \leq 5000\right)~ đỉnh được đánh số từ ~1~ đến ~N~ và ~M~ ~\left(1 \leq M \leq 30000\right)~ 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~ ~\left(1 \leq C \leq 10^9\right)~ giữa nút ~A~ và nút ~B~ ~\left(1 \leq A, B \leq N\right)~. 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~.

Sample Input

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

Sample Output

5

Note

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.pl/problems/FASTFLOW/.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.