MCQUERY - MinCut Query
English | Vietnamese |
You are given a weighted undirected graph with edge weight denoting the capacity of the edge.
Now given a number x, output how many unordered (s,t) pairs are there in the graph such that minCut(s,t) <= x.
A Cut is a partition of the vertices of a graph into two sets such that s and t belong to different set after the partition.
In weighted graphs, the size of a cut is defined to be the sum of weights of the edges crossing the cut. minCut is a cut whose size is the least possible.
Input
First line contains T, the number of test cases.
For each test case the first line contains two integers n and m, denoting the number of vertices and the number of edges in the graph.
Next m lines contain 3 integers u,v,c denoting an undirected of capacity c between vertices u and v; 1 <= u,v <= n.
Next line contains q, the number of queries. Next q line contains one number each which denotes the input x for ith query.
Note: there can be multiple edges between a pair of vertices.
Output
The output for each test case should consist of q lines with one integers in each of them denoting the number of unordered (s,t) pairs corresponding to that query. Output a blank line BETWEEN the test cases.
Note: The timelimit for the problem is somewhat strict.
Example
Input: 1 5 0 1 0 Output: 10
Constraints
Input Set 1: numberOfTestCases <= 15, n <= 40, m <= 400, q <= 10
Input Set 2: numberOfTestCases <= 20, n <= 150, m <= 3000, q <= 30
Edge weights are less than or equal to 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 |