[問題案] Global Minimum Cut of Dynamic Star Augmented Graph

[Pulmn]

(任意) 問題ID: {ID} 問題名: Global Minimum Cut of Dynamic Star Augmented Graph

(任意) 想定アルゴリズム: extreme vertex set を求めて木上でHL分解&セグ木 O(N^2logN+NM+Q(logN)^2) (任意) 参考資料: https://ja.wikipedia.org/wiki/%E6%A5%B5%E7%82%B9%E9%9B%86%E5%90%88

問題概要

（頂点は 0-index とする）N 頂点 M 辺の単純重み付き無向グラフ G が与えられる G の i 番目の辺は ( u_i , v_i ) で重みは w_i である G に新たな頂点 N を加えて、 頂点 j (1<=j<N) と頂点 N に重み a_j の辺を追加した拡張グラフを H とする 以下のクエリを Q 個処理する

・グラフ H の頂点 N と頂点 x_k をつないでいる辺の重みを y_k に変更して H の全域最小カットの重みを求める

入力

N M Q
a_0 a_1 ... 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}

制約

1<=N<=3000 (未定) 0<=M<=min(N*(N-1)/2,10000) 1<=Q<=300,000 (未定) 1<=w_i<=10^9 0<=a_j,y_k<=10^9

検討事項

Star Augmented Graph が適切な用語ではなさそう O(QN) はできるだけ落とすような制約にしたい

[yosupo06]

• https://github.com/yosupo06/library-checker-problems/issues/140 Global Min Cut完全に含んでいますか？(a_0 = INF, a_1 = a2 = ... a{n-1} = 0とかで対応？)
• 解けない…

[yosupo06]

この問題はどこから出てきましたか？　何らかの文献とかからならそこを漁るといい名前がみつかるかもしれません。

[Pulmn]

140 を完全に含んでます

https://www.researchgate.net/publication/31343031_Computing_a_Minimum_Cut_in_a_Graph_with_Dynamic_Edges_Incident_to_a_Designated_Vertex この問題についてはこの文献から出ました http://www.iasi.cnr.it/~ventura/Cargese13/Lectures%20slides/Iwata4.pdf extreme vertex set の計算方法はこのスライドにも載ってます

G → H の拡張操作に star augmentation と名前が付けられていたので、そこから star augmented graph の名前を付けました star augmentation は調べてみたところ他の文献にも使われているので "Global Minimum Cut in(with?) Dynamic Star Augmentation" の方がいいかもしれないですね...

[Pulmn]

https://judge.yosupo.jp/ 問題一覧に反映されていないように見えます

[yosupo06]

わーすいません、直しました