Đa Nguồn Đa Đích
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh có trọng số khả năng thông qua. Có P đỉnh phát (nguồn) và Q đỉnh thu (đích), hai tập đỉnh này rời nhau và mỗi đỉnh chỉ xuất hiện tối đa một lần. Tìm tổng lưu lượng cực đại có thể đẩy từ tập các đỉnh phát đến tập các đỉnh thu.
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 498, 0 ≤ M ≤ 5000).
- Dòng thứ hai: hai số nguyên P và Q (1 ≤ P, Q, P + Q ≤ N).
- Dòng thứ ba: P số nguyên là chỉ số các đỉnh phát.
- Dòng thứ tư: Q số nguyên là chỉ số các đỉnh thu.
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c (1 ≤ u, v ≤ N, 0 ≤ c ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: tổng lưu lượng cực đại.
Ví dụ
| Input | Output |
|---|---|
| 6 7\n2 2\n1 2\n5 6\n1 3 10\n2 3 5\n2 4 8\n3 4 4\n3 5 12\n4 6 10\n4 5 3 | 23 |
Giới hạn
- 2 ≤ N ≤ 498
- 0 ≤ M ≤ 5000
- 0 ≤ c ≤ 10^9
Community Discussion