1082 - 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.