diff options
Diffstat (limited to 'graph/pushRelabel2.cpp')
| -rw-r--r-- | graph/pushRelabel2.cpp | 48 |
1 files changed, 24 insertions, 24 deletions
diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp index 270cd35..5619d88 100644 --- a/graph/pushRelabel2.cpp +++ b/graph/pushRelabel2.cpp @@ -27,39 +27,39 @@ void globalRelabel(int n, int t) { que.assign(n+1, 0); int qh = 0, qt = 0; for (que[qt++] = t; qh < qt;) { - int u = que[qh++], h = height[u] + 1; - for (int id : adj[u]) { + int v = que[qh++], h = height[v] + 1; + for (int id : adj[v]) { if (height[edges[id].to] == n && edges[id ^ 1].c - edges[id ^ 1].f > 0) { ccount[height[edges[id].to] = h]++; que[qt++] = edges[id].to; }}} llist.assign(n+1, {}); dlist.assign(n+1, {}); - for (int u = 0; u < n; u++) { - if (height[u] < n) { - iter[u] = dlist[height[u]].insert(dlist[height[u]].begin(), u); - if (excess[u] > 0) llist[height[u]].push_back(u); + for (int v = 0; v < n; v++) { + if (height[v] < n) { + iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); + if (excess[v] > 0) llist[height[v]].push_back(v); }} highest = highestActive = height[que[qt - 1]]; } -void push(int u, int id) { - int v = edges[id].to; - ll df = min(excess[u], edges[id].c - edges[id].f); +void push(int v, int id) { + int u = edges[id].to; + ll df = min(excess[v], edges[id].c - edges[id].f); edges[id].f += df; edges[id^1].f -= df; - excess[u] -= df; - excess[v] += df; - if (0 < excess[v] && excess[v] <= df) llist[height[v]].push_back(v); + excess[v] -= df; + excess[u] += df; + if (0 < excess[u] && excess[u] <= df) llist[height[u]].push_back(u); } -void discharge(int n, int u) { +void discharge(int n, int v) { int nh = n; - for (int id : adj[u]) { + for (int id : adj[v]) { if (edges[id].c - edges[id].f > 0) { - if (height[u] == height[edges[id].to] + 1) { - push(u, id); - if (!excess[u]) return; + if (height[v] == height[edges[id].to] + 1) { + push(v, id); + if (!excess[v]) return; } else { nh = min(nh, height[edges[id].to] + 1); }}} @@ -71,11 +71,11 @@ void discharge(int n, int u) { } highest = h - 1; } else { - --ccount[h], iter[u] = dlist[h].erase(iter[u]), height[u] = nh; + --ccount[h], iter[v] = dlist[h].erase(iter[v]), height[v] = nh; if (nh == n) return; - ++ccount[nh], iter[u] = dlist[nh].insert(dlist[nh].begin(), u); + ++ccount[nh], iter[v] = dlist[nh].insert(dlist[nh].begin(), v); highest = max(highest, highestActive = nh); - llist[nh].push_back(u); + llist[nh].push_back(v); }} ll maxFlow(int s, int t) { @@ -86,8 +86,8 @@ ll maxFlow(int s, int t) { height.assign(n, 0); height[s] = n; iter.resize(n); - for (int i = 0; i < n; i++) { - if (i != s) iter[i] = dlist[height[i]].insert(dlist[height[i]].begin(), i); + for (int v = 0; v < n; v++) { + if (v != s) iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); } ccount.assign(n, 0); ccount[0] = n-1; @@ -101,9 +101,9 @@ ll maxFlow(int s, int t) { highestActive--; continue; } - int u = llist[highestActive].back(); + int v = llist[highestActive].back(); llist[highestActive].pop_back(); - discharge(n, u); + discharge(n, v); } return excess[t] + inf; } |
