动态星图增广全局最小割（Global Minimum Cut of Dynamic Star Augmented Graph）

问题描述

给定一个简单带权无向图 $G$，含 $N$ 个顶点和 $M$ 条边。第 $i$ 边为 $\{u_i, v_i\}$，权重为 $w_i$。

构造图 $H$：在 $G$ 的基础上新增一个顶点 $N$，并添加 $N$ 条新边 $\{i, N\}$（$i = 0,1,\dots,N-1$），其中边 $\{i, N\}$ 的权重为 $a_i$。

处理 $Q$ 个查询：

• x_i y_i：将边 $\{x_i, N\}$ 的权重更新为 $y_i$（即修改 $a_{x_i} \leftarrow y_i$），然后输出图 $H$ 的全局最小割大小（即删除边集使图不连通的最小总权重）。

约束条件

• $1 \leq N \leq 4000$
• $0 \leq M \leq \min\!\left(\frac{N(N-1)}{2},\, 4000\right)$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq a_i \leq 10^9$
• $0 \leq u_i, v_i < N$
• $u_i \ne v_i$
• $\{u_i, v_i\} \ne \{u_j, v_j\}$（$i \ne j$）
• $0 \leq w_i \leq 10^9$
• $0 \leq x_i < N$
• $0 \leq y_i \leq 10^9$

输入

$N\ M\ Q$
$a_0\ a_1\ \cdots\ a_{N-1}$
$u_0\ v_0\ w_0$
$u_1\ v_1\ w_1$
:
$u_{M-1}\ v_{M-1}\ w_{M-1}$
$x_0\ y_0$
$x_1\ y_1$
:
$x_{Q-1}\ y_{Q-1}$

4 4 11
0 0 0 1
0 1 1
1 2 2
2 3 3
3 0 0
3 0
0 5
1 5
2 5
3 5
0 0
0 5
1 0
1 5
2 0
2 5

0
1
2
3
6
6
3
6
5
6

#2

4 0 6
0 1 2 3
0 0
0 4
1 5
2 6
3 7
0 3

0
1
2
3
4
3