Ghép cặp tối đa

Buổi 18 — BFS & DFS
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$.
Draft saved