Ghép cặp chi phí nhỏ nhất

Buổi 48 — Min-Cost Max Flow
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị hai phía gồm $L$ đỉnh bên trái (đánh số $1..L$), $R$ đỉnh bên phải (đánh số $1..R$) và $M$ cạnh nối. Mỗi cạnh nối $(u, v)$ có trọng số $w$.

Hãy tìm một cặp ghép cực đại (số lượng cạnh ghép được nhiều nhất) sao cho tổng trọng số các cạnh được chọn là nhỏ nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $L, R, M$ ($1 \le L, R \le 150, 0 \le M \le 3000$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u \le L, 1 \le v \le R, 0 \le w \le 10^5$).
Dữ liệu ra
  • In ra hai số nguyên: kích thước cặp ghép cực đại và tổng trọng số nhỏ nhất.
Ví dụ
Input Output
3 3 5
1 1 4
1 2 2
2 2 5
2 3 1
3 1 3
3 6
Giới hạn
  • $1 \le L, R \le 150, 0 \le M \le 3000$.
  • Thời gian chạy: 2 giây.
Draft saved