Phân công công việc tối đa

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

Một công ty có $N$ nhân viên (đánh số $1 \dots N$) và $M$ nhiệm vụ (đánh số $1 \dots M$). Có $E$ mối quan hệ tương thích $(u, v)$ cho biết nhân viên $u$ có thể đảm nhận nhiệm vụ $v$. Mỗi nhân viên chỉ có thể làm tối đa một nhiệm vụ và mỗi nhiệm vụ chỉ do tối đa một nhân viên thực hiện. Hãy tìm số lượng nhiệm vụ nhiều nhất có thể phân công.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, E$.
  • $E$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
  • In ra số lượng nhiệm vụ tối đa có thể phân công.
Ví dụ
Dữ liệu vào Dữ liệu ra
3 3 4
1 1
1 2
2 1
3 2
2
Giới hạn
  • $1 \le N, M \le 1000$
  • $0 \le E \le 50000$
Draft saved