MATCH1 - Cặp ghép không trọng số
Giới hạn- Thời gian: 0.209s
- 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.
Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu là y1, y2, ..., yn.
Một bộ ghép trên G là một tập các cạnh thuộc E đôi một không có đỉnh chung.
Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G.
Chú ý : Dùng
Eof
chứ không dùng
SeekEof.
Input
• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100)
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj) thuộc E.
Output
• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K).
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv).
Example
Input: 4 5 1 1 1 4 2 1 2 2 2 4 3 2 3 3 4 2 4 3 Output: 4 1 1 2 4 3 3 4 2
- Người up: hard7771988
- Nguồn bài: Cuốn DSAP của thầy Lê Minh Hoàng, giáo viên khối chuyên Sư Phạm