File tree 2 files changed +5
-3
lines changed
Filter options
2 files changed +5
-3
lines changed
Original file line number Diff line number Diff line change @@ -55,8 +55,9 @@ It adds an edge oriented from the vertex `from` to the vertex `to` with the capa
55
55
56
56
** @{keyword.complexity}**
57
57
58
- - $O(\min(n^{\frac{2}{3}}m, m^{\frac{3}{2}}))$ (if all the capacities are $1$) or
59
- - $O(n^2 m)$ (general),
58
+ - $O((n + m) \sqrt{m})$ (if all the capacities are $1$),
59
+ - $O(n^2 m)$ (general), or
60
+ - $O(F(n + m))$, where $F$ is the returned value
60
61
61
62
where $m$ is the number of added edges.
62
63
Original file line number Diff line number Diff line change @@ -57,8 +57,9 @@ int graph.add_edge(int from, int to, Cap cap);
57
57
58
58
$m$ を追加された辺数として
59
59
60
- - $O(\min(n^{\frac{2}{3}}m, m^{\frac{3}{2}}) )$ (辺の容量がすべて $1$ の時)
60
+ - $O((n + m) \sqrt{m} )$ (辺の容量がすべて $1$ の時)
61
61
- $O(n^2 m)$
62
+ - 返り値を $F$ として $O(F(n + m))$
62
63
63
64
## min_cut
64
65
You can’t perform that action at this time.
0 commit comments