FFLOW - Fast Maximum Flow
Giới hạn- Thời gian: 0.283s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 ≤ 10 9 ) 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.pl/problems/FASTFLOW/ .
- Người up: racer
- Nguồn bài: Neal Wu - SPOJ