MCQUERY - MinCut Query
English | Vietnamese |
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.
Added by: | Race with time |
Date: | 2009-02-19 |
Time limit: | 1s-2.548s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Code Craft 09 |