Phân công dự án tối ưu
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 |
Community Discussion