Special Edges
Contest: Codeforces Round 659 (Div. 1)
Difficulty rating: 3200
Tags: flows, graphs

Koa the Koala has a directed graph $$$G$$$ with $$$n$$$ nodes and $$$m$$$ edges. Each edge has a capacity associated with it. Exactly $$$k$$$ edges of the graph, numbered from $$$1$$$ to $$$k$$$, are special, such edges initially have a capacity equal to $$$0$$$.

Koa asks you $$$q$$$ queries. In each query she gives you $$$k$$$ integers $$$w_1, w_2, \ldots, w_k$$$. This means that capacity of the $$$i$$$-th special edge becomes $$$w_i$$$ (and other capacities remain the same).

Koa wonders: what is the maximum flow that goes from node $$$1$$$ to node $$$n$$$ after each such query?

Help her!

Input format:
The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$k$$$, $$$q$$$ ($$$2 \le n \le 10^4$$$, $$$1 \le m \le 10^4$$$, $$$1 \le k \le \min(10, m)$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of nodes, the number of edges, the number of special edges and the number of queries.

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \le u, v \le n$$$; $$$0 \le w \le 25$$$) — the description of a directed edge from node $$$u$$$ to node $$$v$$$ with capacity $$$w$$$.

Edges are numbered starting from $$$1$$$ in the same order they are listed in the input. The first $$$k$$$ edges are the special edges. It is guaranteed that $$$w_i = 0$$$ for all $$$i$$$ with $$$1 \le i \le k$$$.

Each of the next $$$q$$$ lines contains $$$k$$$ integers $$$w_1, w_2, \ldots, w_k$$$ ($$$0 \le w_i \le 25$$$)  — the description of the query. $$$w_i$$$ denotes the capacity of $$$i$$$-th edge.

Output format:
For the $$$i$$$-th query, print one integer $$$res_i$$$  — the maximum flow that can be obtained from node $$$1$$$ to node $$$n$$$ given the $$$i$$$-th query's special edge weights.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
For the second sample, the following images correspond to the first two queries (from left to right respectively). For each edge there is a pair flow/capacity denoting flow pushed through the edge and edge's capacity. The special edges are colored in red.

As you can see in first query maximum flow from node $$$1$$$ to node $$$4$$$ equals $$$0$$$ and in second query equals $$$1$$$.

Example input:
2 1 1 3
1 2 0
0
1
2

Example output:
0
1
2

Example input:
4 4 2 5
1 2 0
2 3 0
2 4 5
3 4 2
0 0
1 10
10 0
7 1
7 2

Example output:
0
1
5
6
7

Editorial:
Finding maximum flow from $$$1$$$ to $$$n$$$ is equivalent to find the minimum cut from $$$1$$$ to $$$n$$$. Let's use the later interpretation to solve the problem.
Suppose there is a single special edge ($$$k = 1$$$), on each query there are two options, either this edge belong to the minimum cut or it doesn't. If the edge doesn't belong to the minimum cut, the value of the cut won't change even if we increase the capacity of each edge arbitrarily (let's say to $$$\infty$$$). On the other hand, if the edge belong to the cut, then the value of the cut will be equal to the capacity of the edge + the value of the cut if the capacity of the edge was $$$0$$$. With this in mind we can compute each query in O(1).
Let $$$MC_0$$$ be the value of the minimum cut if the capacity of the special edge is 0, and $$$MC_{\infty}$$$ be the value of the minimum cut if the capacity of the special edge is $$$\infty$$$. Then for each query $$$c_i$$$ the minimum cut will be equal to $$$min(MC_{\infty}, MC_0 + c_i)$$$.
We can generalize this ideas to multiple edges in the following way. For each subset of special edges, they either belong to the minimum cut, or they don't. If we fix a subset $$$S$$$ and say those are among the special edges the only ones that belong to the minimum cut, then the value of the cut will be equal to the sum of the values of the capacities of these edges plus the minimum cut in the graph were each of these edges has capacity 0 and other special edges has capacity $$$\infty$$$. In a similar way as we did for the case of $$$k=1$$$ we can pre-compute $$$2^k$$$ cuts, fixing $$$S$$$ as each possible set in $$$O(2^k \cdot max\_flow(n, m))$$$, and then answer each query in $$$O(2^k)$$$. The overall complexity of this solution will be $$$O(2^k \cdot max\_flow(n, m) + q \cdot 2^k)$$$.
However the preprocessing can be done faster. If we have the maximum flow (and the residual network) for a mask, we can compute the maximum flow adding one new edge in $$$O(w * m)$$$, doing at most $$$w$$$ steps of augmentation as done by Ford-Fulkerson algorithm. To remove an edge we just store the residual network before augmenting, in such a way that we can undo the last change. The time complexity of the preprocessing will be $$$O(max\_flow(n, m) + 2^k \cdot w \cdot m)$$$ and since we need to be able to undo the last operation spatial complexity will be $$$O(k \cdot m)$$$.
It was possible to solve the problem without the last trick, but it was not guaranteed that slow flows implementations would work in $$$O(2^k \cdot max\_flow(n, m))$$$.