Phân Cụm Máy Chủ Hai Trung Tâm

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

Có N máy chủ (1..N), mỗi máy chủ phải được đặt vào Trung tâm A hoặc Trung tâm B.

  • Đặt máy i ở A tốn chi phí a_i, đặt ở B tốn chi phí b_i.
  • Có M cặp (u, v, w): nếu u và v đặt ở hai trung tâm khác nhau, phát sinh thêm chi phí truyền tải w.
  • Có K1 cặp (u, v, s): nếu cả u và v cùng đặt ở A, được giảm chi phí s.
  • Có K2 cặp (u, v, s): nếu cả u và v cùng đặt ở B, được giảm chi phí s.

Tìm tổng chi phí nhỏ nhất có thể (có thể âm nếu tiền giảm vượt quá chi phí).

Dữ liệu vào
  • Dòng đầu: bốn số nguyên N, M, K1, K2 (1 ≤ N, N + K1 + K2 ≤ 498, 0 ≤ M ≤ 1500).
  • Dòng thứ hai: N số nguyên a_1, ..., a_N.
  • Dòng thứ ba: N số nguyên b_1, ..., b_N.
  • M dòng tiếp theo: u, v, w.
  • K1 dòng tiếp theo: u, v, s.
  • K2 dòng tiếp theo: u, v, s.
Dữ liệu ra
  • Một số nguyên duy nhất: tổng chi phí nhỏ nhất.
Ví dụ
Input Output
3 1 1 1\n5 5 5\n6 6 6\n1 2 3\n1 2 4\n2 3 8 10
Giới hạn
  • N + K1 + K2 ≤ 498, M ≤ 1500
  • 0 ≤ a_i, b_i, w, s ≤ 10^9
Draft saved