Phủ Cạnh Tối Thiểu
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị hai phía gồm $N$ đỉnh phía trái, $M$ đỉnh phía phải và $E$ cạnh nối giữa hai phía.
Một tập cạnh $F$ được gọi là tập phủ cạnh (Edge Cover) nếu mọi đỉnh của đồ thị (cả $N + M$ đỉnh) đều là đầu mút của ít nhất một cạnh trong $F$.
Hãy tìm kích thước nhỏ nhất của một tập phủ cạnh, hoặc in ra -1 nếu không tồn tại tập phủ cạnh nào.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N, M \le 50\,000$, $0 \le E \le 150\,000$).
- $E$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u \le N$, $1 \le v \le M$).
Dữ liệu ra
- Một số nguyên duy nhất là kích thước tập phủ cạnh tối thiểu, hoặc
-1nếu không tồn tại.
Ví dụ
Input
3 3 4
1 1
1 2
2 2
3 3
Output
3
Giải thích
Tất cả các đỉnh đều có bậc $\ge 1$. Cặp ghép cực đại có kích thước $3$, nên tập phủ cạnh tối thiểu có kích thước $3 + 3 - 3 = 3$.
Giới hạn
- $1 \le N, M \le 50\,000$
- $0 \le E \le 150\,000$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion