Skip to content

Instantly share code, notes, and snippets.

@Chillee Chillee/dinic.cpp
Last active May 18, 2019

Embed
What would you like to do?
Max Flow (Dinic's, HLPP)
template <int MAXV, class T = int> struct Dinic {
const static bool SCALING = false; // non-scaling = V^2E, Scaling=VElog(U) with higher constant
int lim = 1;
const T INF = numeric_limits<T>::max();
struct edge {
int to, rev;
T cap, flow;
};
int s = MAXV - 2, t = MAXV - 1;
int level[MAXV], ptr[MAXV];
vector<edge> adj[MAXV];
void addEdge(int a, int b, T cap, bool isDirected = true) {
adj[a].push_back({b, adj[b].size(), cap, 0});
adj[b].push_back({a, adj[a].size() - 1, isDirected ? 0 : cap, 0});
}
bool bfs() {
queue<int> q({s});
fill(all(level), -1);
level[s] = 0;
while (!q.empty() && level[t] == -1) {
int v = q.front();
q.pop();
for (auto e : adj[v]) {
if (level[e.to] == -1 && e.flow < e.cap && (!SCALING || e.cap - e.flow >= lim)) {
q.push(e.to);
level[e.to] = level[v] + 1;
}
}
}
return level[t] != -1;
}
T dfs(int v, T flow) {
if (v == t || !flow)
return flow;
for (; ptr[v] < adj[v].size(); ptr[v]++) {
edge &e = adj[v][ptr[v]];
if (level[e.to] != level[v] + 1)
continue;
if (T pushed = dfs(e.to, min(flow, e.cap - e.flow))) {
e.flow += pushed;
adj[e.to][e.rev].flow -= pushed;
return pushed;
}
}
return 0;
}
long long calc() {
long long flow = 0;
for (lim = SCALING ? (1 << 30) : 1; lim > 0; lim >>= 1) {
while (bfs()) {
fill(all(ptr), 0);
while (T pushed = dfs(s, INF))
flow += pushed;
}
}
return flow;
}
};
template <int MAXN, class T = int> struct HLPP {
const T INF = numeric_limits<T>::max();
struct edge {
int to, rev;
T f;
};
int s = MAXN - 1, t = MAXN - 2;
vector<edge> adj[MAXN];
vector<int> lst[MAXN], gap[MAXN];
T excess[MAXN];
int highest, height[MAXN], cnt[MAXN], work;
void addEdge(int from, int to, int f, bool isDirected = true) {
adj[from].push_back({to, adj[to].size(), f});
adj[to].push_back({from, adj[from].size() - 1, isDirected ? 0 : f});
}
void updHeight(int v, int nh) {
work++;
if (height[v] != MAXN)
cnt[height[v]]--;
height[v] = nh;
if (nh == MAXN)
return;
cnt[nh]++, highest = nh;
gap[nh].push_back(v);
if (excess[v] > 0)
lst[nh].push_back(v);
}
void globalRelabel() {
work = 0;
fill(all(height), MAXN);
fill(all(cnt), 0);
for (int i = 0; i < highest; i++)
lst[i].clear(), gap[i].clear();
height[t] = 0;
queue<int> q({t});
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : adj[v])
if (height[e.to] == MAXN && adj[e.to][e.rev].f > 0)
q.push(e.to), updHeight(e.to, height[v] + 1);
highest = height[v];
}
}
void push(int v, edge &e) {
if (excess[e.to] == 0)
lst[height[e.to]].push_back(e.to);
T df = min(excess[v], e.f);
e.f -= df, adj[e.to][e.rev].f += df;
excess[v] -= df, excess[e.to] += df;
}
void discharge(int v) {
int nh = MAXN;
for (auto &e : adj[v]) {
if (e.f > 0) {
if (height[v] == height[e.to] + 1) {
push(v, e);
if (excess[v] <= 0)
return;
} else
nh = min(nh, height[e.to] + 1);
}
}
if (cnt[height[v]] > 1)
updHeight(v, nh);
else {
for (int i = height[v]; i <= highest; i++) {
for (auto j : gap[i])
updHeight(j, MAXN);
gap[i].clear();
}
}
}
T calc(int heur_n = MAXN) {
fill(all(excess), 0);
excess[s] = INF, excess[t] = -INF;
globalRelabel();
for (auto &e : adj[s])
push(s, e);
for (; highest >= 0; highest--) {
while (!lst[highest].empty()) {
int v = lst[highest].back();
lst[highest].pop_back();
discharge(v);
if (work > 4 * heur_n)
globalRelabel();
}
}
return excess[t] + INF;
}
};
@Chillee

This comment has been minimized.

Copy link
Owner Author

commented Mar 18, 2019

Both of these implementations are very fast, although the HLPP one is faster. On all of these problems, this HLPP implementation is the fastest submission/tied for the fastest.

Dinic's:
SPOJ FASTFLOW (ran without scaling): 0.04
SPOJ FASTFLOW (ran with scaling): 0.27
VNSPOJ FASTFLOW (ran with scaling): 0.00 (1st!)
VNSPOJ FASTFLOW (ran without scaling): TLE
Weird Chinese Flow Problem that's trying to force you to use HLPP (https://loj.ac/problem/127): 88 points with scaling, 44 without

HLPP:
SPOJ FASTFLOW: 0.00 (1st)
VNSPOJ FASTFLOW: 0.00 (1st)
LOJ: 100 pts, 1087 ms (1st)

@Chillee

This comment has been minimized.

Copy link
Owner Author

commented Mar 29, 2019

One limitation of the HLPP implementation is that you can't recover the weights for the full flow - use Dinic's for this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.