Ghép cặp chi phí nhỏ nhất
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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.
Community Discussion