8224: [yosupo] Graph - Global Minimum Cut of Dynamic Star Augmented Graph
[Creator : ]
Description
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:
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$.
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}$
$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}$
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$
$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$
Sample 1 Input
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
Sample 1 Output
0
1
2
3
6
1
6
3
6
5
6
Sample 2 Input
4 0 6
0 1 2 3
0 0
0 4
1 5
2 6
3 7
0 3
Sample 2 Output
0
1
2
3
4
3