Phân Rã Dòng Chảy

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

Cho một đồ thị có hướng không chu trình (DAG) gồm N đỉnh và M cạnh đơn phân biệt, cùng với một luồng hợp lệ từ đỉnh 1 đến đỉnh N (mỗi cạnh có lưu lượng f > 0, bảo toàn luồng tại các đỉnh 2..N-1). Hãy phân rã luồng này thành các đường đi từ 1 đến N bằng thuật toán tham lam: ở mỗi bước, chọn đường đi có thứ tự từ điển nhỏ nhất gồm các cạnh còn lưu lượng dương và đẩy tối đa lưu lượng có thể dọc theo đường đi đó.

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (2 ≤ N ≤ 500, 0 ≤ M ≤ 5000).
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, f (1 ≤ u < v ≤ N, 1 ≤ f ≤ 10^12).
Dữ liệu ra
  • Dòng đầu: số nguyên K là số lượng đường đi.
  • K dòng tiếp theo, mỗi dòng ghi: lưu lượng đường đi, số lượng đỉnh trên đường đi, và dãy các đỉnh từ 1 đến N.
Ví dụ
Input Output
4 5\n1 2 5\n1 3 3\n2 3 2\n2 4 3\n3 4 5 3\n2 4 1 2 3 4\n3 3 1 2 4\n3 3 1 3 4
Giới hạn
  • 2 ≤ N ≤ 500
  • 0 ≤ M ≤ 5000
  • 1 ≤ f ≤ 10^12
Draft saved