Phân Cụm Máy Chủ Hai Trung Tâm
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề 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
Community Discussion