Lưu Lượng Có Cận Dưới

Buổi 47 — Luồng cực đại (Dinic)
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved