Ghép Đôi Công Nhân Và Máy Móc
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Một nhà máy có $N$ công nhân (đánh số từ $1$ đến $N$) và $M$ máy móc (đánh số từ $1$ đến $M$). Có $K$ cặp $(u, v)$ cho biết công nhân $u$ có thể vận hành máy $v$.
Mỗi công nhân chỉ có thể vận hành tối đa một máy và mỗi máy chỉ được vận hành bởi tối đa một công nhân. Hãy tìm số lượng cặp công nhân - máy móc tối đa có thể ghép đôi đồng thời.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($1 \le N, M \le 500$, $0 \le K \le N \cdot M$).
- $K$ 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à số cặp ghép đôi tối đa.
Ví dụ
| Input | Output |
|---|---|
| 3 3 4 1 1 1 2 2 2 3 3 |
3 |
Giới hạn
- $1 \le N, M \le 500$
- $0 \le K \le N \cdot M$
Community Discussion