Ghép Cặp Ưu Tiên

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

Đề bài

Có $N$ ứng viên (đánh số $1$ đến $N$) và $M$ vị trí công việc (đánh số $1$ đến $M$). Có $E$ cạnh $(u, v)$ cho biết ứng viên $u$ phù hợp với công việc $v$.

Trong đó, $K$ ứng viên đầu tiên (từ $1$ đến $K$) là các ứng viên ưu tiên. Ban tuyển dụng muốn tìm một phép phân công sao cho:

  1. Tổng số ứng viên được nhận việc là lớn nhất có thể.
  2. Trong số các phương án có tổng số người được nhận việc lớn nhất, số lượng ứng viên ưu tiên được nhận việc là lớn nhất.

Hãy in ra hai số: tổng số ứng viên được nhận việc tối đa, và số ứng viên ưu tiên được nhận việc tối đa.

Dữ liệu vào

  • Dòng đầu tiên chứa bốn số nguyên $N, M, E, K$ ($1 \le N, M \le 20\,000$, $0 \le E \le 80\,000$, $0 \le K \le N$).
  • $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

  • In ra hai số nguyên cách nhau bởi dấu cách: tổng số cặp ghép tối đa và số lượng đỉnh thuộc ${1, \dots, K}$ được ghép tối đa.

Ví dụ

Input
3 2 3 1
1 1
2 1
2 2
Output
2 1

Giải thích

Tổng số cặp ghép tối đa là $2$: chọn $(1, 1)$ và $(2, 2)$, khi đó ứng viên ưu tiên $1$ được ghép.

Giới hạn

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