Phân Công Dự Án Có Hạn Mức
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
Community Discussion