Ghép cặp tối đa
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Có $N_1$ ứng viên (đánh số từ $1$ đến $N_1$) và $N_2$ công việc (đánh số từ $1$ đến $N_2$). Có $M$ mối quan hệ phù hợp dạng $(u, v)$, nghĩa là ứng viên $u$ có thể làm công việc $v$. Mỗi ứng viên chỉ nhận tối đa 1 công việc và mỗi công việc chỉ giao cho tối đa 1 ứng viên. Hãy tìm số lượng cặp ghép tối đa có thể.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N_1, N_2, M$ ($1 \le N_1, N_2 \le 500$, $0 \le M \le 5000$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u \le N_1$, $1 \le v \le N_2$).
Dữ liệu ra
- In ra một số nguyên duy nhất là kích thước cặp ghép cực đại.
Ví dụ
| Input | Output |
|---|---|
| 3 3 4 1 1 1 2 2 1 3 2 |
2 |
| 3 3 0 | 0 |
Giới hạn
- $1 \le N_1, N_2 \le 500$, $0 \le M \le 5000$.
Community Discussion