Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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 V1, V2 sao cho mỗi cạnh thuộc E đều có dạng v1v2 với v1 thuộc V1, v2 thuộc V2. 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 pi có thể làm công việc ji thì có một cạnh giữa hai đỉnh pi và ji 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 xi, yj.

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

Được gửi lên bởi:Duc
Ngày:2008-01-06
Thời gian chạy:0.442s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2014-11-22 02:19:36 Tenga
Ma trn k 6s :|
2014-11-15 10:31:55 Con Bò Huyền Thoại
test yếu quá, nhầm m, n mà vẫn dc 90 điểm
2014-08-14 15:01:15 Thcs Ðặng Chánh Kỷ
test yếu quá, đồ thị này có lẽ thưa nên vẫn qua được
2013-09-16 08:24:31 vo van dong
cho e hoi ý tưởng của bài toan nay với
2013-03-31 16:26:54 anh thoi
tìm bài viết vs code đâu vậy ad
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.