Voltar

## Algoritmo de Dinic - Grafos

0 Curtidas
```int last_edge[MAXV], cur_edge[MAXV], dist[MAXV];
int prev_edge[MAXE], cap[MAXE], flow[MAXE], adj[MAXE];
int nedges;

void d_init() {
nedges = 0;
memset(last_edge, -1, sizeof last_edge);
}

void d_edge(int v, int w, int capacity, bool r = false) {
prev_edge[nedges] = last_edge[v];
cap[nedges] = capacity;
flow[nedges] = 0;
last_edge[v] = nedges++;

if(!r) d_edge(w, v, 0, true);
}

bool d_auxflow(int source, int sink) {
queue q;
q.push(source);

memset(dist, -1, sizeof dist);
dist[source] = 0;
memcpy(cur_edge, last_edge, sizeof last_edge);

while(!q.empty()) {
int v = q.front(); q.pop();
for(int i = last_edge[v]; i != -1; i = prev_edge[i]) {
if(cap[i] - flow[i] == 0) continue;

if(dist[adj[i]] == -1) {
dist[adj[i]] = dist[v] + 1;

if(adj[i] == sink) return true;
}
}
}

return false;
}

int d_augmenting(int v, int sink, int c) {
if(v == sink) return c;

for(int& i = cur_edge[v]; i != -1; i = prev_edge[i]) {
if(cap[i] - flow[i] == 0 || dist[adj[i]] != dist[v] + 1)
continue;

int val;
if(val = d_augmenting(adj[i], sink, min(c, cap[i] - flow[i]))) {
flow[i] += val;
flow[i^1] -= val;
return val;
}
}

return 0;
}

int dinic(int source, int sink) {
int ret = 0;
while(d_auxflow(source, sink)) {
int flow;
while(flow = d_augmenting(source, sink, 0x3f3f3f3f))
ret += flow;
}

return ret;
}
```