Đa Nguồn Đa Đích

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