Skip to content

Commit 0495145

Browse files
suisen-cpsuisen-cp
committed
fix Readme of MaxFlow/MinCostFlow
1 parent de81778 commit 0495145

2 files changed

Lines changed: 31 additions & 50 deletions

File tree

‎MaxFlow/Readme.md‎

Lines changed: 12 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -38,16 +38,10 @@ public void addEdge(int from, int to, long cap)
3838
public long maxFlow(int s, int t)
3939
// (2)
4040
public long flow(int s, int t, long flowLimit)
41-
// (3)
42-
public long fordFulkersonMaxFlow(int s, int t)
43-
// (4)
44-
public long fordFulkersonFlow(int s, int t, long flowLimit)
4541
```
4642

4743
- (1): 頂点 `s` から `t` へ流せる限り流し、流せた量を返す。Dinic のアルゴルズムを用います。
4844
- (2) 頂点 `s` から `t` へ流量 `flowLimit` に達するまで流せる限り流し、流せた量を返す。Dinic のアルゴルズムを用います。
49-
- (3) 頂点 `s` から `t` へ流せる限り流し、流せた量を返す。FordFulkerson のアルゴルズムを用います。
50-
- (4) 頂点 `s` から `t` へ流量 `flowLimit` に達するまで流せる限り流し、流せた量を返す。FordFulkerson のアルゴルズムを用います。
5145
- 複数回呼んだ場合は，前回流したフローからの差分が返ります。
5246

5347
制約
@@ -60,7 +54,6 @@ public long fordFulkersonFlow(int s, int t, long flowLimit)
6054

6155
- (1), (2) $O(\min(n^{2/3}*m, m^{3/2}))$ (辺の容量がすべて 1 の時)
6256
- (1), (2) $O(n^2*m)$
63-
- (3), (4) 返り値を `f` として，`O(f*m)`
6457

6558
### minCut
6659

@@ -76,34 +69,34 @@ public boolean[] minCut(int s)
7669

7770
### getEdge / getEdges
7871

79-
`getEdge`、`getEdges` の返り値には以下のメソッドを持つ `MaxFlow.CapEdge` 型が用いられています。
72+
`getEdge`、`getEdges` の返り値には以下のメンバを持つ `MaxFlow.CapEdge` 型が用いられています。
8073

8174
```java
8275
class CapEdge {
8376
// (1)
84-
public int getFrom()
77+
public final int from;
8578
// (2)
86-
public int getTo()
79+
public final int to;
8780
// (3)
88-
public long getCap()
81+
public final long cap;
8982
// (4)
90-
public long getFlow()
83+
public final long flow;
9184
};
9285
```
9386

94-
- (1): 始点を返します。計算量: $O(1)$
95-
- (2): 終点を返します。計算量: $O(1)$
96-
- (3): 現在の容量を返します。計算量: $O(1)$
87+
- (1): 辺の始点を返します。計算量: $O(1)$
88+
- (2): 辺の終点を返します。計算量: $O(1)$
89+
- (3): 辺の容量を返します。計算量: $O(1)$
9790
- (4): 現在の流量を返しまず。計算量: $O(1)$
9891

9992
```java
10093
// (1)
10194
public CapEdge getEdge(int i)
10295
// (2)
103-
public java.util.ArrayList<CapEdge> getEdges()
96+
public CapEdge[] getEdges()
10497
```
10598

106-
今の内部の辺の状態を返す。辺の順番は `addEdge` で追加された順番と同一。
99+
現在の内部の辺の状態を返す。辺の順番は `addEdge` で追加された順番と同一。
107100

108101
制約
109102

@@ -112,7 +105,7 @@ public java.util.ArrayList<CapEdge> getEdges()
112105
計算量
113106

114107
- (1): $O(1)$
115-
- (2): $O(1)$
108+
- (2): $O(m)$
116109

117110
### changeEdge
118111

@@ -132,4 +125,4 @@ $O(1)
132125

133126
## 使用例
134127

135-
[AtCoder Library Practice Contest D - Maxflow](https://atcoder.jp/contests/practice2/submissions/16646346)
128+
[AtCoder Library Practice Contest D - Maxflow](https://atcoder.jp/contests/practice2/submissions/20808482)

‎MinCostFlow/Readme.md‎

Lines changed: 19 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -35,12 +35,12 @@ public int addEdge(int from, int to, long cap, long cost)
3535

3636
```java
3737
// (1)
38-
public long[] minCostMaxFlow(int s, int t)
38+
public MinCostFlow.FlowAndCost minCostMaxFlow(int s, int t)
3939
// (2)
40-
public long[] minCostFlow(int s, int t, long flowLimit)
40+
public MinCostFlow.FlowAndCost minCostFlow(int s, int t, long flowLimit)
4141
```
4242

43-
`s` から `t` へ流せるだけ流し、その流量とコストを返す。返り値は長さ 2 の配列で表現され、中身は `{flow, cost}` である。
43+
`s` から `t` へ流せるだけ流し、その流量とコストを返す。返り値は `MinCostFlow.FlowAndCost` であり，メンバに `long flow` と `long cost` を持つ．
4444

4545
- (1): `s` から `t` へ流せるだけ流す
4646
- (2): `s` から `t` へ流量 `flowLimit` まで流せるだけ流す
@@ -57,9 +57,9 @@ public long[] minCostFlow(int s, int t, long flowLimit)
5757

5858
```java
5959
// (1)
60-
public java.util.ArrayList<long[]> minCostSlope(int s, int t)
60+
public java.util.ArrayList<MinCostFlow.FlowAndCost> minCostSlope(int s, int t)
6161
// (2)
62-
public java.util.ArrayList<long[]> minCostSlope(int s, int t, long flowLimit)
62+
public java.util.ArrayList<MinCostFlow.FlowAndCost> minCostSlope(int s, int t, long flowLimit)
6363
```
6464

6565
返り値に流量とコストの関係の折れ線が入る。全ての `x` について、流量 `x` の時の最小コストを `g(x)` とすると、`{x, g(x)}` は返り値を折れ線として見たものに含まれる。返り値のリストは以下のような性質を満たします。
@@ -73,54 +73,42 @@ public java.util.ArrayList<long[]> minCostSlope(int s, int t, long flowLimit)
7373
制約
7474

7575
- `s != t`
76-
- `minCostSlope` や `minCostFlow` を合わせて複数回呼んだときの挙動は未定義 (複数回フローを流す場合は後述の `clearFlow` メソッドによりフローをリセットしてください)
76+
- `minCostSlope` や `minCostFlow` を合わせて複数回呼んだときの挙動は未定義
7777

7878
計算量
7979

8080
`F` を流量、`m` を追加した辺の本数として $O(F (n + m) \log n)$
8181

82-
### clearFlow
83-
84-
```java
85-
public void clearFlow()
86-
```
87-
88-
全ての辺に流れているフローを 0 にします。
89-
90-
計算量
91-
92-
`m` を追加した辺の本数として $O(n + m)$
93-
9482
### getEdge / getEdges
9583

9684
`getEdge`、`getEdges` の返り値には以下のメソッドを持つ `MinCostFlow.WeightedCapEdge` 型が用いられています。
9785

9886
```java
9987
class WeightedCapEdge {
10088
// (1)
101-
public int getFrom()
89+
public final int from;
10290
// (2)
103-
public int getTo()
91+
public final int to;
10492
// (3)
105-
public long getCap()
93+
public final long cap;
10694
// (4)
107-
public long getCost()
95+
public final long flow;
10896
// (4)
109-
public long getFlow()
97+
public final long cost;
11098
};
11199
```
112100

113-
- (1): 始点を返します。計算量: $O(1)$
114-
- (2): 終点を返します。計算量: $O(1)$
115-
- (3): 現在の容量を返します。計算量: $O(1)$
116-
- (4): コストを返します。計算量: $O(1)$
101+
- (1): 辺の始点を返します。計算量: $O(1)$
102+
- (2): 辺の終点を返します。計算量: $O(1)$
103+
- (3): 辺の容量を返します。計算量: $O(1)$
104+
- (4): 辺のコストを返します。計算量: $O(1)$
117105
- (5): 現在の流量を返しまず。計算量: $O(1)$
118106

119107
```java
120108
// (1)
121-
public CapEdge getEdge(int i)
109+
public WeightedCapEdge getEdge(int i)
122110
// (2)
123-
public java.util.ArrayList<WeightedCapEdge> getEdges()
111+
public WeightedCapEdge[] getEdges()
124112
```
125113

126114
今の内部の辺の状態を返す。辺の順番は `addEdge` で追加された順番と同一。
@@ -132,8 +120,8 @@ public java.util.ArrayList<WeightedCapEdge> getEdges()
132120
計算量
133121

134122
- (1): $O(1)$
135-
- (2): $O(1)$
123+
- (2): $O(m)$
136124

137125
使用例
138126

139-
[AtCoder Library Practice Contest E - MinCostFlow](https://atcoder.jp/contests/practice2/submissions/16654383)
127+
[AtCoder Library Practice Contest E - MinCostFlow](https://atcoder.jp/contests/practice2/submissions/20811599)

0 commit comments

Comments
 (0)