← 返回题目列表

Codeforces · 1383/F

F. 特殊边缘

中文机器翻译题面 查看原题

Koa 考拉有一个有向图 $$$G$$$,具有 $$$n$$$ 节点和 $$$m$$$ 边。每条边都有与其关联的容量。图中的 $$$k$$$ 边(从 $$$1$$$ 到 $$$k$$$ 编号)是特殊的,这些边最初的容量等于 $$$0$$$。

Koa 询问您 $$$q$$$ 查询。在每个查询中,她都会给你 $$$k$$$ 整数 $$$w_1, w_2, \ldots, w_k$$$。这意味着第$$$i$$$个特殊边的容量变为$$$w_i$$$(其他容量保持不变)。

Koa 想知道:每次这样的查询之后,从节点 $$$1$$$ 到节点 $$$n$$$ 的最大流量是多少?

帮助她!

输入

输入的第一行包含四个整数 $$$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$$$) — 节点数、边数、特殊边数和查询数。

接下来的 $$$m$$$ 行包含三个整数 $$$u$$$、$$$v$$$、$$$w$$$ ($$$1 \le u, v \le n$$$; $$$0 \le w \le 25$$$) - 从节点 $$$u$$$ 到节点 $$$v$$$ 且具有容量的有向边的描述$$$w$$$。

边从 $$$1$$$ 开始编号,顺序与输入中列出的顺序相同。前 $$$k$$$ 边是特殊边。对于所有 $$$i$$$ 且 $$$1 \le i \le k$$$ 的情况,保证 $$$w_i = 0$$$。

接下来的 $$$q$$$ 行包含 $$$k$$$ 整数 $$$w_1, w_2, \ldots, w_k$$$ ($$$0 \le w_i \le 25$$$) — 查询的描述。 $$$w_i$$$表示第$$$i$$$条边的容量。

输出

对于第 $$$i$$$ 个查询,打印一个整数 $$$res_i$$$ — 给定第 $$$i$$$ 个查询的特殊边权重,从节点 $$$1$$$ 到节点 $$$n$$$ 可以获得的最大流量。

示例

输入 #1

2 1 1 3
1 2 0
0
1
2

输出 #1

0
1
2

输入 #2

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

输出 #2

0
1
5
6
7

注意

对于第二个示例,以下图像对应于前两个查询(分别从左到右)。对于每条边,都有一对流量/容量,表示通过该边的流量和边的容量。特殊边缘为红色。

正如您在第一个查询中看到的,从节点 $$$1$$$ 到节点 $$$4$$$ 的最大流量等于 $$$0$$$,在第二个查询中等于 $$$1$$$。