Skip to content

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit c70fcae

Browse filesBrowse files
authored
Merge pull request #161 from yosupo06/patch/maxflow
fix time complexty of maxflow
2 parents 16897e5 + c1c9fbe commit c70fcae
Copy full SHA for c70fcae

File tree

2 files changed

+5
-3
lines changed
Filter options

2 files changed

+5
-3
lines changed

‎document_en/maxflow.md

Copy file name to clipboardExpand all lines: document_en/maxflow.md
+3-2
Original file line numberDiff line numberDiff line change
@@ -55,8 +55,9 @@ It adds an edge oriented from the vertex `from` to the vertex `to` with the capa
5555

5656
**@{keyword.complexity}**
5757

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
6061

6162
where $m$ is the number of added edges.
6263

‎document_ja/maxflow.md

Copy file name to clipboardExpand all lines: document_ja/maxflow.md
+2-1
Original file line numberDiff line numberDiff line change
@@ -57,8 +57,9 @@ int graph.add_edge(int from, int to, Cap cap);
5757

5858
$m$ を追加された辺数として
5959

60-
- $O(\min(n^{\frac{2}{3}}m, m^{\frac{3}{2}}))$ (辺の容量がすべて $1$ の時)
60+
- $O((n + m) \sqrt{m})$ (辺の容量がすべて $1$ の時)
6161
- $O(n^2 m)$
62+
- 返り値を $F$ として $O(F(n + m))$
6263

6364
## min_cut
6465

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.