Ghép cặp cực đại trên đồ thị hai phía nhỏ
Ghép cặp hai phía là bài toán xếp việc: một bên là người, một bên là công việc, mỗi cạnh là
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Ghép cặp hai phía là bài toán xếp việc: một bên là người, một bên là công việc, mỗi cạnh là một người có thể làm được một việc. Muốn xếp được nhiều cặp nhất có thể, mỗi người chỉ nhận một việc và mỗi việc chỉ giao cho một người, người ta tìm ghép cặp cực đại.
Yêu cầu
Cho một đồ thị hai phía: bên trái gồm n đỉnh đánh số 1..n, bên phía phải gồm m đỉnh đánh số 1..m, và e cạnh nối một đỉnh bên trái với một đỉnh bên phải. Mỗi dòng cạnh có dạng u v nghĩa là đỉnh trái u ghép được với đỉnh phải v.
Một cách ghép cặp là một tập cạnh mà không đỉnh nào bị dùng hai lần. Hãy in ra số cạnh lớn nhất của một cách ghép cặp như vậy.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: ba số nguyên n m e (1 <= n, m <= 4, 1 <= e <= 7).
- e dòng tiếp theo: mỗi dòng hai số nguyên u v (1 <= u <= n, 1 <= v <= m).
- Mỗi cặp (u, v) chỉ xuất hiện một lần.
Output
Một số nguyên duy nhất: kích thước ghép cặp cực đại.
Ràng buộc
- Đồ thị là hai phía, không có cạnh nối hai đỉnh cùng một bên.
- Mỗi cặp (u, v) chỉ xuất hiện một lần.
- Mỗi đỉnh chỉ được dùng tối đa một lần trong một cách ghép cặp.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
2 2 2
1 1
2 2
Output
2
Ví dụ 2
Input
3 3 3
1 1
1 2
2 1
Output
2
Giải thích
Dữ liệu vào:
Đỉnh trái 1 ghép được với hai đỉnh phải 1, 2; đỉnh trái 2 chỉ ghép được với đỉnh phải 1; đỉnh trái 3 không ghép được với ai. Cách tốt nhất: ghép 1 với 2 và ghép 2 với 1, được 2 cặp. Kết quả in ra là 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
