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$ とする.

以下の $Q$ 個のクエリを処理せよ.

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

Constraints
制約

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

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions