Adding-the-maximum-flow arc
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 300
Solved: 76
- Description
- In the network G(s, t, N, A, U)(s: the souce node, t: the sink node, N: the set of the nodes, A: the set of the arcs, U: the set of the capacity of the arcs), adding a arc's capacity with one unit may make the maximum flow larger. We call this arc as the adding-the-maximum-flow arc.
Now the problem is that giving a network G, you must calculate the number of the the adding-the-maximum-flow arcs in the network G. - Input
- The first line of the input contains an integer T, giving the number of the test cases.
For each test case: The first line contains four integers: n, m, s and t(0 < n <= 400, 0 < m <= 10000, 0 < s, t <= n), giving the number of nodes, the number of arcs, the source node and the sink node.
And there are m lines followed: each line describe an arc: a, b, c, the arc is from a to b and its capacity is c(0 < a, b <= n, 0 < c < 1000). - Output
- For each test case, the output contains a single integer which is the number of the adding-the-maximum flow arcs.
- sample input
-
1 4 4 1 4 1 2 3 1 3 5 2 4 2 3 4 6
- sample output
-
2
- hint
- There may be multiarcs in the network, that is to say there may be more than one arc between two nodes.
- source
- Liu sh