Flow in a Dynamic Network#4589
There is a given directed network on which two types of operations can be performed. The first operation increases by the capacity of the edge from to , and the second operation decreases by the capacity of the edge from to .
Your task is to output the value of the maximum flow in the network from vertex to vertex after each of the operations.
The first line contains two integers and (2 \leq n \leq 150, 0 \leq m \leq 2000), where is the number of vertices in the network, and is the number of edges. The next lines describe the edges: each line contains three integers , , and (1 \leq x, y \leq n, 1 \leq c \leq 1000), denoting a directed edge from to with capacity .
The next line contains an integer (1 \leq t \leq 500), the number of operations. The following lines contain the operations, each specified as either "1 x y" or "2 x y" depending on the type.
At any moment, the network does not contain multiple edges between the same pair of vertices or self-loops. The capacity of any edge is always non-negative.
Output t + 1 numbers. First, print the value of the maximum flow in the network before any operations are performed. Next, after each operation, output the value of the maximum flow in the current network.
Example 1