Đạt Ngưỡng Lưu Lượng

Buổi 47 — Luồng cực đại (Dinic)
Points
20
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, M cạnh có trọng số khả năng thông qua. Kiểm tra xem có thể truyền được lưu lượng ít nhất là K đơn vị từ đỉnh 1 đến đỉnh N hay không.

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 500, 0 ≤ M ≤ 5000).
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c (1 ≤ u, v ≤ N, 0 ≤ c ≤ 10^9).
  • Dòng cuối: số nguyên K (0 ≤ K ≤ 10^15).
Dữ liệu ra
  • In "YES" nếu lưu lượng cực đại từ 1 đến N lớn hơn hoặc bằng K, ngược lại in "NO".
Ví dụ
Input Output
4 5\n1 2 10\n1 3 5\n2 3 15\n2 4 5\n3 4 10\n15 YES
4 5\n1 2 10\n1 3 5\n2 3 15\n2 4 5\n3 4 10\n16 NO
Giới hạn
  • 2 ≤ N ≤ 500
  • 0 ≤ M ≤ 5000
  • 0 ≤ c ≤ 10^9
Draft saved