Phân công dự án tối ưu

Buổi 67-68 — Mock IOI
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Một công ty có $N$ dự án đánh số từ $1$ đến $N$. Dự án thứ $i$ mang lại lợi nhuận ròng là $p_i$ (có thể âm nếu là dự án đầu tư hạ tầng).

Có $M$ ràng buộc phụ thuộc dạng $(u, v)$: nếu chọn thực hiện dự án $u$, bắt buộc phải thực hiện dự án $v$. Bạn có thể chọn một tập con bất kỳ các dự án (kể cả tập rỗng với lợi nhuận $0$) thỏa mãn mọi ràng buộc. Hãy tìm tổng lợi nhuận lớn nhất có thể.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 500$, $0 \le M \le 5000$).
  • Dòng thứ hai chứa $N$ số nguyên $p_1, p_2, \dots, p_N$ ($-10^9 \le p_i \le 10^9$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N, u \neq v$).

Kết quả

In ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất có thể.

Subtasks

  • Subtask 1 (25%): $N \le 20$.
  • Subtask 2 (35%): Đồ thị phụ thuộc là một cây có hướng.
  • Subtask 3 (40%): Không có ràng buộc thêm.

Ví dụ

Input Output
4 3
10 -5 8 -10
1 2
3 2
3 4
5
Draft saved