Phủ Cạnh Tối Thiểu

Buổi 49 — Matching (Hopcroft-Karp)
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề 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 -1 nế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
Draft saved