Hợp Đồng Cộng Hưởng

Buổi 47 — Luồng cực đại (Dinic)
Points
72
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved