Ghép cặp công nhân và công việc
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ công nhân (đánh số $1..N$) và $M$ công việc (đánh số $1..M$). Có $K$ cặp $(u, v)$ cho biết công nhân $u$ có thể làm công việc $v$. Mỗi công nhân chỉ làm tối đa $1$ công việc và mỗi công việc chỉ giao cho tối đa $1$ công nhân. Hãy tìm số lượng cặp ghép tối đa.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$.
- $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
In ra một số nguyên duy nhất là số cặp ghép tối đa.
Ví dụ
| Input | Output |
|---|---|
| 3 3 4 1 1 1 2 2 1 3 3 |
3 |
Giới hạn
$1 \le N, M \le 5 \cdot 10^4$, $0 \le K \le 1.5 \cdot 10^5$.
Community Discussion