Ghép Đôi Trọng Số Cực Đại

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

Đề bài

Cho một đồ thị hai phía có trọng số gồm $N$ đỉnh phía trái, $M$ đỉnh phía phải và $E$ cạnh. Mỗi cạnh $(u, v)$ có trọng số nguyên dương $w$.

Hãy chọn một tập các cạnh không chung đỉnh (một cặp ghép) sao cho tổng trọng số của các cạnh được chọn là lớn nhất có thể. (Không bắt buộc mọi đỉnh đều phải được ghép).

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N, M \le 400$, $0 \le E \le N \times M$).
  • $E$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u \le N$, $1 \le v \le M$, $1 \le w \le 10^9$). Nếu có nhiều cạnh nối cùng cặp $(u, v)$, lấy cạnh có trọng số lớn nhất.

Dữ liệu ra

  • Một số nguyên duy nhất là tổng trọng số lớn nhất của cặp ghép.

Ví dụ

Input
3 3 4
1 1 10
1 2 5
2 2 8
3 1 7
Output
18

Giải thích

Chọn cạnh $(1, 1)$ trọng số $10$ và $(2, 2)$ trọng số $8$, tổng là $18$. (Cạnh $(3, 1)$ không được chọn vì đỉnh $1$ phía phải đã ghép).

Giới hạn

  • $1 \le N, M \le 400$
  • $0 \le E \le N \times M$
  • $1 \le w \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved