Trạm Trung Chuyển Quá Tải

Buổi 47 — Luồng cực đại (Dinic)
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Hệ thống vận chuyển gồm N trạm (1 đến N) và M tuyến đường một chiều. Không chỉ các tuyến đường có giới hạn tải trọng c, bản thân mỗi trạm i cũng chỉ xử lý được tối đa w_i đơn vị hàng hóa đi qua. Hãy tìm lượng hàng tối đa có thể chuyển từ trạm 1 đến trạm N.

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 250, 0 ≤ M ≤ 4000).
  • Dòng thứ hai: N số nguyên w_1, w_2, ..., w_N (0 ≤ w_i ≤ 10^9).
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ c ≤ 10^9).
Dữ liệu ra
  • Một số nguyên duy nhất: lưu lượng cực đại từ trạm 1 đến trạm N.
Ví dụ
Input Output
4 5\n100 4 6 100\n1 2 10\n1 3 10\n2 3 5\n2 4 10\n3 4 10 10
Giới hạn
  • 2 ≤ N ≤ 250
  • 0 ≤ M ≤ 4000
  • 0 ≤ w_i, c ≤ 10^9
Draft saved