Giải các bài toán quy hoạch vận tải, phân việc và chia nhóm tối ưu bằng mô hình luồng trên mạng với các thuật toán hiện đại có độ phức tạp thấp.
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Xây dựng đồ thị có hướng với dung lượng cạnh và cạnh đảo dung lượng 0.
Phân tầng đồ thị bằng BFS và tìm đường tăng luồng nghẽn bằng DFS.
Quy đổi bài toán cặp ghép về mạng luồng nguồn S và đích T.
Quên cập nhật dung lượng của cạnh đảo khi tăng luồng.
Không reset mảng phân tầng level[] sau mỗi pha BFS của thuật toán Dinic.
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
Cho một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh có trọng số. Xây dựng cây Gomory-Hu và trả lời Q truy vấn: mỗi truy vấn yêu cầu tìm giá trị lát cắt hẹp nhất giữa 2 đỉnh u v…
Cho một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh có trọng số dương. Hãy tìm giá trị lát cắt hẹp nhất toàn cục (Global Min-Cut).
Cho một đồ thị hai phía gồm tập đỉnh trái U (N đỉnh) và tập đỉnh phải V (M đỉnh). Có E cạnh vô hướng có trọng số nối giữa một đỉnh thuộc tập trái và một đỉnh thuộc tập phải.
Có N công việc và N công nhân. Chi phí để công nhân i thực hiện công việc j là Ci, j. Mỗi công nhân chỉ làm đúng 1 việc và mỗi việc chỉ được giao cho đúng 1 công nhân. Hãy tìm c…
Cho một mạng gồm N đỉnh và M cung có hướng. Cung thứ i đi từ đỉnh ui đến đỉnh vi có:
Có N công nhân (đánh số 1 … N) và N công việc (đánh số 1 … N).
Cho một đồ thị hai phía gồm tập đỉnh trái có N đỉnh (đánh số từ 1 đến N) và tập đỉnh phải có M đỉnh (đánh số từ 1 đến M). Có K cạnh nối giữa các đỉnh tập trái và tập phải.
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
Hệ thống truyền dẫn dữ liệu huấn luyện của AI Empire Academy gồm N trạm mạng (2 ≤ N ≤ 500) và M đường truyền dẫn một chiều (1 ≤ M ≤ 5000). Mỗi đường truyền từ trạm u đến tr…
Cho một mạng luồng có hướng gồm N đỉnh (2 ≤ N ≤ 1000) và M cạnh (1 ≤ M ≤ 10000). Mỗi cạnh có dung lượng c ≥ 0. Hãy tính luồng cực đại từ đỉnh 1 đến đỉnh N.
Cho một mạng luồng có hướng gồm N đỉnh (2 ≤ N ≤ 300) và M cạnh (1 ≤ M ≤ 3000). Mỗi cạnh từ u đến v có dung lượng c ≥ 0 và chi phí truyền tải w cho mỗi đơn vị luồng.
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh. Cho trước hai đỉnh phân biệt S và T không có cạnh nối trực tiếp giữa chúng.
Cho đồ thị hai phía với tập đỉnh trái gồm N đỉnh (đánh số 1 … N) và tập đỉnh phải gồm M đỉnh (đánh số 1 … M). Có E cạnh vô hướng nối giữa một đỉnh thuộc tập trái và một đỉn…
Cho đồ thị hai phía gồm hai tập đỉnh L (gồm các đỉnh {0, 1, …, |L|-1}) và R (gồm các đỉnh {0, 1, …, |R|-1}). Có M cạnh nối giữa một đỉnh thuộc L và một đỉnh thuộc R.