ACL_グラフ
グラフ
コンストラクタdsu.DSU(n)$ O(n)
$ n 頂点を用意する
制約：$ 0 \le n \le 10^8 （おそらくPythonでは無制限）
辺の追加 .merge(a, b)$ O(\alpha(n))※計算量について後述
$ a,b 間に辺を張る
制約：$ 0 \le a, b \lt n
return :連結後の代表元
連結判定 .same(a, b)$ O(\alpha(n))※
$ a, b が連結か調べる
制約：$ 0 \le a, b \lt n
return :連結ならTrue
代表元の取得.leader(a)$ O(\alpha(n))※
$ a のいる連結成分の代表元を得る
制約：$ 0 \le a \lt n
return :代表元
サイズの取得 .size(a)$ O(\alpha(n))※
$ a のいる連結成分の仲間の数を得る
制約：$ 0 \le a \lt n
return :連結成分の仲間の数
全グループの情報を取得.groups()$ O(n)
「各グループのメンバーリスト」のリストを得る
順番はテキトー決まってない
return :「各グループのメンバーリスト」のリスト
※ならし$ O(\alpha(n)) 。最悪は$ O(\log n) という噂
MaxFlow 最大流maxflow
コンストラクタmaxflow.MFGraph(n)$ O(n)
$ n 頂点を用意する
制約：$ 0 \le n \le 10^8 （おそらくPythonでは無制限）
辺の追加.add_edge(src, dst, cap)$ O(1)
srcからdstへ容量capの辺を張る。ついでに辺の番号も得る
制約：$ 0 \le src, dst$ \lt n , $ 0 \le cap
return :今張った辺の番号
最大流 .flow(s, t, flow_limit=None)容量1:$ O(\min(n^{\frac{2}{3}}m,m^{\frac{3}{2}}))容量任意:$ O(n^2m)
sからtへ最大flow_limit流して、流せた量を得る
複数回呼んでもOK
制約：$ s \not = t
return :流せた量
最小カット .min_cut(s)$ O(n+m)
最小カットしたときsからたどり着ける頂点を得る。先に.flow(s, t)しておくこと。
return :たどりつける頂点番号がTrueな長さ$ n のリスト
1辺を取得.get_edge(i)$ O(1)
辺$ i の情報を得る
src:始点、dst:終点、cap:容量、flow:流量 のEdge型
辺を取得.edges()$ O(m)
すべての辺の情報を得る
辺を変更.change_edge(i, new_cap, new_flow)$ O(1)
辺$ i の容量をnew_capに、流量をnew_flowに更新する
MinCostFlow 最小費用流mincostflow
コンストラクタmincostflow.MCFGraph(n)$ O(n)
$ n 頂点を用意する
制約：$ 0 \le n \le 10^8 （おそらくPythonでは無制限）
辺の追加.add_edge(src, dst, cap, cost)$ O(1)
srcからdstへ容量capコストcostの辺を張る。ついでに辺の番号を得る
制約：$ 0 \le src, dst$ \lt n , $ 0 \le cap, cost
return :今張った辺の番号
最小費用流.flow(s, t, flow_limit=None)$ O(F(n+m)\log(n+m))
sからtへ最大flow_limit流して、流せた量とそのときのコストを得る
複数回呼べない
制約：$ s \not = t
return :(流せた量,かかったコスト) のtuple
費用=f(流量)を計算.slope(s, t, flow_limit=None)$ O(F(n+m)\log(n+m))
流量$ x に対する最小費用$ y = g(x) の、折れる部分の座標$ (x, g(x)) を得る
複数回呼べない
制約：$ s \not = t
return :[(流す量,かかるコスト)] のList[tuple]
1辺を取得.get_edge(i)$ O(1)
辺$ i の情報を得る
src:始点、dst:終点、cap:容量、flow:流量、cost:コスト のEdge型
辺を取得.edges()$ O(m)
すべての辺の情報を得る
SCC 強連結成分分解scc
コンストラクタscc.SCCGraph(n)$ O(n)
$ n 頂点を用意する
制約：$ 0 \le n
辺の追加.add_edge(from_vertex, to_vertex)$ O(1)
from_vertexからto_vertexに有向辺を張る
制約：$ 0 \le from_vertex, to_vertex$ \lt n
分解.scc()$ O(n+m)
「強連結成分の中身リスト」のリストがトポロジカルソートされたものを得る
return :「各強連結成分の中身」のリスト List[List[int]]
2-SATtwosat
コンストラクタtwosat.TwoSAT(n)$ O(n)
$ n 変数で用意する
制約：$ 0 \le n
条件の追加.add_clause(i, f, j, g)$ O(1)
$ (x_i = f) \lor (x_j = g) を追加する
f, gはboolで
条件判定.satisfiable()$ O(n+m)
条件を満たせるか判定する
複数回呼んでもOK
return :満たせる組み合わせがあるならTrue
具体例の取得.answer()$ O(n)
満たせる割当の一例を取得する。先に.satisfiable()しておく
答えがないときには呼ばないほうがいいヨ
return :満たせる割当になってる長さ$ n のリスト