# Global Minimum Cut of Dynamic Star Augmented Graph

AC一覧

## Problem Statement問題文

You are given a simple weighted undirected graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is $\lbrace u_i, v_i \rbrace$ and has a weight of $w_i$.

Let $H$ be a graph obtained by adding a new vertex $N$ to $G$ together with new $N$ edges. The $i$-th edge is $\lbrace i, N \rbrace$ and has a weight of $a_i$.

Process the following $Q$ queries in order:

• change a weight of an edge $\lbrace x_i,N \rbrace$ to $y_i$ and print a global minmum cut size in $H$.

$N$ 頂点 $M$ 辺の単純重み付き無向グラフ $G$ が与えられる．$i$ 番目の辺は頂点 $u_i$,$v_i$ 間に張られており，重みは $w_i$ である．

$G$ に新たな頂点 $N$ を追加して，頂点 $i$,$N$ 間に重み $a_i$ の辺を張ることによって得られるグラフを $H$ とする．

• $H$ 上の頂点 $x_i$,$N$ 間に張られている辺の重みを $y_i$ に変更して，$H$ の全域最小カットの重みを出力する．

## Constraints制約

• $1 \le N \le 4{,}000$
• $0 \le M \le \min ( \frac{N(N-1)}{2} , 4{,}000 )$
• $1 \le Q \le 200{,}000$
• $0 \le a_i \le 10^{9}$
• $0 \le u_i, v_i \lt N$
• $u_i \neq v_i$
• $\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$
• $0 \le w_i \le 10^{9}$
• $0 \le x_i \lt N$
• $0 \le y_i \le 10^{9}$

## Input入力

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


## Sampleサンプル

### # 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
1
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


Timelimit: 10 secs

Before submitting, please confirm terms and conditions