diff options
| author | mzuenni <michi.zuendorf@gmail.com> | 2023-03-28 13:25:59 +0200 |
|---|---|---|
| committer | mzuenni <michi.zuendorf@gmail.com> | 2023-03-28 13:25:59 +0200 |
| commit | fe5fa1141efeb7454c763dbd2645fb4ff04487a3 (patch) | |
| tree | f2197bb94ce80ab2fae886177dfa9b0bd11538ac /graph/minCostMaxFlow.cpp | |
| parent | 3b91d2662310aee532cc84e1447824459671767e (diff) | |
merged
Diffstat (limited to 'graph/minCostMaxFlow.cpp')
| -rw-r--r-- | graph/minCostMaxFlow.cpp | 14 |
1 files changed, 9 insertions, 5 deletions
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp index 27f6b34..d6d0586 100644 --- a/graph/minCostMaxFlow.cpp +++ b/graph/minCostMaxFlow.cpp @@ -23,13 +23,15 @@ struct MinCostFlow { } bool SPFA() { - pref.assign(sz(adjlist), - 1); + pref.assign(sz(adjlist), -1); dist.assign(sz(adjlist), INF); vector<bool> inqueue(sz(adjlist)); queue<int> queue; - dist[s] = 0; queue.push(s); - pref[s] = s; inqueue[s] = true; + dist[s] = 0; + queue.push(s); + pref[s] = s; + inqueue[s] = true; while (!queue.empty()) { int cur = queue.front(); queue.pop(); @@ -39,9 +41,11 @@ struct MinCostFlow { if (edges[id].f > 0 && dist[to] > dist[cur] + edges[id].cost) { dist[to] = dist[cur] + edges[id].cost; - pref[to] = cur; con[to] = id; + pref[to] = cur; + con[to] = id; if (!inqueue[to]) { - inqueue[to] = true; queue.push(to); + inqueue[to] = true; + queue.push(to); }}}} return pref[t] != -1; } |