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.
There are multiple test case in the input file, terminated by EOF. 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.
Constraints
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. There is no need to print any blank lines between test cases.
Note: The timelimit for the problem is somewhat strict.
1 5 0 1 0
10
Migrated from old NTUJ.
CodeCraft'09
| No. | Testdata Range | Score |
|---|