Lát Cắt Tối Thiểu

Buổi 47 — Luồng cực đại (Dinic)
Points
22
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ông âm. Bạn cần chọn một tập cạnh để xóa sao cho không còn đường đi có hướng nào từ đỉnh s đến đỉnh t, đồng thời tổng trọng số các cạnh bị xóa là nhỏ nhất.

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 500, 0 ≤ M ≤ 5000).
  • Dòng thứ hai: hai số nguyên s và t (1 ≤ s, t ≤ N, s ≠ t).
  • 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 trọng số nhỏ nhất của lát cắt (s, t).
Ví dụ
Input Output
4 5\n1 4\n1 2 3\n1 3 2\n2 3 1\n2 4 2\n3 4 3 5
Giới hạn
  • 2 ≤ N ≤ 500
  • 0 ≤ M ≤ 5000
  • 0 ≤ c ≤ 10^9
Draft saved