NKBM - Cặp ghép cực đại trên đồ thị hai phía
Giới hạn- Thời gian: 0.442s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trong lý thuyết đồ thị, một cặp ghép hay tập cạnh độc lập của một đồ thị là một tập các cạnh không có đỉnh chung. Bài toán ghép cặp thường được quan tâm trong trường hợp đồ thị hai phía . Đồ thị đơn vô hướng G=(V,E) là một đồ thị hai phía nếu như tồn tại một cách phân hoạch tập đinh V thành hai tập V 1 , V 2 sao cho mỗi cạnh thuộc E đều có dạng v 1 v 2 với v 1 thuộc V 1 , v 2 thuộc V 2 . Một ví dụ đó là bài toán sắp xếp công việc. Giả sử có P người và J công việc, mỗi người có thể làm một số công việc nào đó. Ta mô hình bài toán bằng một đồ thị hai phía với P+J đỉnh. Nếu người p i có thể làm công việc j i thì có một cạnh giữa hai đỉnh p i và j i trên đồ thị.
Tìm một cặp ghép cực đại (còn được gọi là cặp ghép có lực lượng lớn nhất ) trên một đồ thị hai phía G=(V=(X,Y), E) là một bài toán quen thuộc và đơn giản trong lý thuyết đồ thị. Định lý Konig chỉ ra rằng trong một đồ thị hai phía, kích thước của cặp ghép cực đại bằng kích thước của phủ đỉnh nhỏ nhất . Từ kết quả này, bài toán phủ đỉnh nhỏ nhất và bài toán tập độc lập lớn nhất trên đồ thị hai phía có thể giải được trong thời gian đa thức.
Bạn hãy thử giải quyết bài toán tìm cặp ghép cực đại trên đồ thị hai phía: cho biết đồ thị hai phía G=(V=(X,Y), E), hãy tìm cặp ghép cực đại (có nhiều cạnh nhất).
Dữ liệu
- Dòng đầu tiên chứa hai số x, y, m (x, y ≤ 1000), theo thứ tự là số đỉnh thuộc tập X, tập Y của đồ thị và số cạnh nối.
- m dòng tiếp theo mỗi dòng ghi hai số i, j cách nhau bởi một dấu cách thể hiện có cạnh nối giữa hai đỉnh x i , y j .
Kết qủa
In ra kích thước của cặp ghép cực đại.
Ví dụ
Dữ liệu: 4 5 9 1 1 1 4 2 1 2 2 2 4 3 2 3 3 4 2 4 3 Kết qủa 4
- Người up: paulmcvn