Lưu Lượng Có Cận Dưới
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh. Mỗi cạnh thứ i đi từ u đến v có cận dưới l và cận trên r (0 ≤ l ≤ r). Một luồng hợp lệ từ đỉnh 1 đến đỉnh N phải thỏa mãn l ≤ f(e) ≤ r với mọi cạnh e và bảo toàn luồng tại mọi đỉnh trung gian (2..N-1). Hãy tìm giá trị luồng hợp lệ cực đại từ 1 đến N, hoặc in -1 nếu không tồn tại luồng hợp lệ nào.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 498, 0 ≤ M ≤ 4800).
- M dòng tiếp theo, mỗi dòng chứa bốn số nguyên u, v, l, r (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ l ≤ r ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: luồng cực đại hợp lệ từ 1 đến N, hoặc -1 nếu vô nghiệm.
Ví dụ
| Input | Output |
|---|---|
| 4 5\n1 2 2 10\n1 3 1 5\n2 3 0 4\n2 4 3 8\n3 4 2 10 | 15 |
Giới hạn
- 2 ≤ N ≤ 498
- 0 ≤ M ≤ 4800
- 0 ≤ l ≤ r ≤ 10^9
Community Discussion