Skip to content

Navigation Menu

Sign in
Appearance settings

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 c1c9fbe

Browse filesBrowse files
committed
fix time complexty of maxflow
1 parent 198f33d commit c1c9fbe
Copy full SHA for c1c9fbe

File tree

Expand file treeCollapse file tree

2 files changed

+5
-3
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+5
-3
lines changed

‎document_en/maxflow.md

Copy file name to clipboardExpand all lines: document_en/maxflow.md
+3-2Lines changed: 3 additions & 2 deletions
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-1Lines changed: 2 additions & 1 deletion
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.