Lựa Chọn Dự Án

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

Có N dự án (1..N), dự án i mang lại lợi nhuận p_i (có thể âm nếu là chi phí). Có M điều kiện phụ thuộc dạng (u, v): nếu chọn dự án u thì bắt buộc phải chọn dự án v. Tìm tổng lợi nhuận lớn nhất có thể đạt được (có thể không chọn dự án nào để nhận 0).

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 498, 0 ≤ M ≤ 5000).
  • Dòng thứ hai: N số nguyên p_1, p_2, ..., p_N (-10^9 ≤ p_i ≤ 10^9).
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N, u ≠ v).
Dữ liệu ra
  • Một số nguyên duy nhất: tổng lợi nhuận lớn nhất.
Ví dụ
Input Output
4 3\n10 -4 -5 8\n1 2\n1 3\n4 3 9
Giới hạn
  • 1 ≤ N ≤ 498
  • 0 ≤ M ≤ 5000
  • -10^9 ≤ p_i ≤ 10^9
Draft saved