Phân Công Dự Án Có Hạn Mức

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

Đề bài

Có $N$ kỹ sư (đánh số $1$ đến $N$) và $M$ dự án (đánh số $1$ đến $M$). Dự án $v$ cần tối đa $c_v$ kỹ sư tham gia. Mỗi kỹ sư chỉ có thể tham gia tối đa $1$ dự án, và có $E$ cặp $(u, v)$ cho biết kỹ sư $u$ có thể làm dự án $v$.

Hãy tìm số lượng kỹ sư nhiều nhất có thể phân công vào các dự án.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N \le 20\,000$, $1 \le M \le 500$, $0 \le E \le 80\,000$).
  • Dòng thứ hai chứa $M$ số nguyên $c_1, c_2, \dots, c_M$ ($1 \le c_v \le 50$).
  • $E$ 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ố kỹ sư nhiều nhất được phân công.

Ví dụ

Input
4 2 5
2 1
1 1
2 1
3 1
3 2
4 2
Output
3

Giải thích

Dự án 1 nhận kỹ sư 1 và 2; dự án 2 nhận kỹ sư 3 (hoặc 4). Tổng cộng 3 kỹ sư được phân công.

Giới hạn

  • $1 \le N \le 20\,000$, $1 \le M \le 500$
  • $1 \le c_v \le 50$
  • $0 \le E \le 80\,000$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved