Phân Rã Dòng Chảy
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
Community Discussion