Cặp ghép cực đại trên đồ thị hai phía

View as PDF

Submit solution


Points: 0.16 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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).

Input

  • Dòng đầu tiên chứa hai số ~x~, ~y~, ~m~ ~(x~, ~y \leq 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}~.

Output

  • In ra kích thước của cặp ghép cực đại.

Sample Input

4 5 9
1 1
1 4
2 1
2 2
2 4
3 2
3 3
4 2
4 3

Sample Output

4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.