Phủ Đỉnh Có Trọng Số

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

Đề bài

Cho một đồ thị hai phía gồm $N$ đỉnh phía trái và $M$ đỉnh phía phải cùng $E$ cạnh nối giữa hai phía.

Mỗi đỉnh $u$ phía trái có trọng số $w_u$, và mỗi đỉnh $v$ phía phải có trọng số $c_v$. Một tập đỉnh $S$ được gọi là tập phủ đỉnh nếu mọi cạnh $(u, v)$ đều có ít nhất một đầu mút thuộc $S$.

Theo mở rộng có trọng số của định lý König, hãy tìm tổng trọng số nhỏ nhất của một tập phủ đỉnh trong đồ thị hai phía đã cho.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N, M \le 1000$, $0 \le E \le 20\,000$).
  • Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$ ($1 \le w_u \le 10^9$).
  • Dòng thứ ba chứa $M$ số nguyên $c_1, c_2, \dots, c_M$ ($1 \le c_v \le 10^9$).
  • $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à tổng trọng số nhỏ nhất của tập phủ đỉnh.

Ví dụ

Input
2 2 3
10 5
4 8
1 1
1 2
2 2
Output
12

Giải thích

Chọn đỉnh $1$ phía trái (trọng số $10$)? Không, chọn đỉnh $1$ phía phải ($4$) và đỉnh $2$ phía phải ($8$) được tổng $12$. Hoặc chọn đỉnh $2$ phía trái ($5$) và đỉnh $1, 2$ phía phải? Không, chọn $L_1$ ($10$) và $L_2$ ($5$) là $15$, chọn $R_1$ ($4$) và $R_2$ ($8$) là $12$ phủ được tất cả 3 cạnh.

Giới hạn

  • $1 \le N, M \le 1000$
  • $0 \le E \le 20\,000$
  • $1 \le w_u, c_v \le 10^9$
  • Thời gian: 3 giây
  • Bộ nhớ: 256 MB
Draft saved