← 返回题目列表

Codeforces · 903/G

G. 又一个最大流问题

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

在这个问题中,您将不得不处理一个非常特殊的网络。

网络由两部分组成:A部分和B部分。每个部分由n个顶点组成; A 部分的第 i 个顶点表示为 Ai,B 部分的第 i 个顶点表示为 Bi。

对于每个索引 i (1 ≤ i < n),分别存在从顶点 Ai 到顶点 Ai + 1 以及从 Bi 到 Bi + 1 的有向边。这些边的容量在输入中给出。此外,可能存在多个从 A 部分到 B 部分(但绝不会从 B 到 A)的有向边。

您必须计算该网络中从 A1 到 Bn 的最大流量值。连接 Ai 到 Ai + 1 的边的容量有时可能会发生变化,并且您还必须在这些变化后保持最大流量值。除此之外,网络是固定的(B 部分没有变化,从 A 到 B 的边没有变化,也没有边插入或删除)。

看一下示例和注释可以更好地理解网络的结构。

输入

第一行包含三个整数 n、m 和 q (2 ≤ n, m ≤ 2·105, 0 ≤ q ≤ 2·105) — 分别是每个部分的顶点数、从 A 到 B 的边数和变化数。

接下来是 n - 1 行,第 i 行包含两个整数 xi 和 yi,表示从 Ai 到 Ai + 1 的边的容量为 xi,从 Bi 到 Bi + 1 的边的容量为 yi (1 ≤ xi, yi ≤ 109)。

接下来是 m 行,描述从 A 到 B 的边。每行包含三个整数 x、y 和 z,表示从 Ax 到 By 的边,容量为 z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 109)。从 Ax 到 By 可能有多条边。

接下来是 q 行,描述网络的一系列更改。第i行包含两个整数vi和wi,表示从Avi到Avi + 1的边的容量设置为wi(1≤vi<n,1≤wi≤109)。

输出

首先打印原网络中的最大流量值。然后打印q个整数,其中第i个整数必须等于第i次更改后的最大流量值。

示例

输入 #1

4 3 2
1 2
3 4
5 6
2 2 7
1 4 8
4 3 9
1 100
2 100

输出 #1

9
14
14

注意

这是示例中的原始网络: