Truy Vết Lát Cắt Hẹp Nhất

Buổi 47 — Luồng cực đại (Dinic)
Points
42
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 (đánh số từ 1 đến M), cạnh thứ i nối từ u đến v với công suất c. Hãy tìm giá trị lát cắt cực tiểu giữa đỉnh 1 và đỉnh N, đồng thời liệt kê chỉ số các cạnh thuộc lát cắt cực tiểu (S, T) sao cho tập đỉnh S (chứa đỉnh 1) có số lượng đỉnh ít nhất.

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, c (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ c ≤ 10^9).
Dữ liệu ra
  • Dòng đầu: hai số nguyên F và K — giá trị lát cắt cực tiểu và số lượng cạnh trong lát cắt.
  • Dòng thứ hai: K số nguyên là chỉ số các cạnh trong lát cắt (theo thứ tự tăng dần), hoặc dòng trống nếu K = 0.
Ví dụ
Input Output
4 5\n1 2 3\n1 3 2\n2 3 1\n2 4 2\n3 4 3 5 2\n1 2
Giới hạn
  • 2 ≤ N ≤ 500
  • 0 ≤ M ≤ 5000
  • 0 ≤ c ≤ 10^9
Draft saved