MCQUERY - MinCut Query
Giới hạn- Thời gian: 2.548s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một đồ thị vô hướng có trọng số, với trọng số cạnh thể hiện khả năng thông qua của cạnh đó.
Bây giờ cho một số x, hãy tính xem có bao nhiêu cặp (s, t) không tính thứ tự trong đồ thị thỏa mãn minCut(s,t) <= x.
Một nhát cắt là một cách chia các đỉnh của đồ thị thành 2 tập hợp sao cho s và t thuộc 2 tập khác nhau sau khi chia.
Trong đồ thị có trọng số, độ lớn của một nhát cắt được định nghĩa là tổng trọng số của các cạnh bị nhát cắt cắt qua. minCut là một nhát cắt có độ lớn nhỏ nhất có thể.
Input
Dòng đầu chứa T, số lượng test.
Với mỗi test, dòng đầu chứa 2 số nguyên n và m, thể hiện số lượng đỉnh và số lượng cạnh của đồ thị.
m dòng tiếp theo, mỗi dòng chứa 3 số nguyên u,v,c thể hiện một cạnh vô hướng với khả năng thông qua c giữa đỉnh u và v; 1 <= u,v <= n.
Dòng tiếp theo chứa q, số lượng câu hỏi. q dòng tiếp theo, mỗi dòng chứa một số nguyên x.
Lưu ý: có thể có nhiều cạnh giữa một cặp đỉnh.
Output
Chứa q dòng, mỗi dòng chứa 1 số nguyên thể hiện số lượng cặp không thứ tự (s, t) tương ứng cho câu hỏi đó. In ra một dòng trống giữa các test.
Lưu ý: Time limit cho bài này khá chặt.
Example
Input: 1 5 0 1 0 Output: 10
Constraints
Input Set 1: Số lượng test <= 15, n <= 40, m <= 400, q <= 10
Input Set 2: Số lượng test <= 20, n <= 150, m <= 3000, q <= 30
Trọng số các cạnh không quá 10^6.
- Người up: racer
- Nguồn bài: Code Craft 09