Hợp Đồng Cộng Hưởng
Points
72
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Có N mô-đun phần mềm (1..N), kích hoạt mô-đun i tốn chi phí c_i. Có M quan hệ phụ thuộc (u, v): nếu kích hoạt mô-đun u thì bắt buộc phải kích hoạt mô-đun v. Có K hợp đồng (a, b, w): nếu cả hai mô-đun a và b đều được kích hoạt, bạn nhận được khoản thưởng w. Tìm lợi nhuận ròng lớn nhất (tổng thưởng trừ tổng chi phí).
Dữ liệu vào
- Dòng đầu: ba số nguyên N, M, K (1 ≤ N, K, N + K ≤ 498, 0 ≤ M ≤ 2000).
- Dòng thứ hai: N số nguyên c_1, ..., c_N (0 ≤ c_i ≤ 10^9).
- M dòng tiếp theo: hai số nguyên u, v (1 ≤ u, v ≤ N, u ≠ v).
- K dòng tiếp theo: ba số nguyên a, b, w (1 ≤ a, b ≤ N, 0 ≤ w ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: lợi nhuận ròng lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 1 2\n4 3 5\n1 2\n1 2 10\n2 3 6 | 4 |
Giới hạn
- N + K ≤ 498, M ≤ 2000
- 0 ≤ c_i, w ≤ 10^9
Community Discussion