## Algoritmo de MaxFlow.

Cualquier duda no dudes en contactar.

``````/**
* Author: Eric
* Description: Returns maximum flow.
* Time: O(V^2 * E) for general graphs. For unit capacities O(min(V^(2/3), E^(1/2)) * E). For maximum matching O(E*sqrt(V)))(bipartite unit weighted graf). It is generally very fast.
* Status: Tested
* Usage: To obtain a cut in the mincut problem one must bfs from the source. All the vertices reached from it using only edges with CAP > 0 are in the same cut
*/

typedef long long ll;
typedef vector<int> vi;
const ll INF = 1000000000000000000LL;

#define VEI(w,e) ((E[e].u == w) ? E[e].v : E[e].u)
#define CAP(w,e) ((E[e].u == w) ? E[e].cap[0] - E[e].flow : E[e].cap[1] + E[e].flow)
#define ADD(w,e,f) E[e].flow += ((E[e].u == w) ? (f) : (-(f)))

struct Edge { int u, v; ll cap[2], flow; };

vi d, act;

bool bfs(int s, int t, vector<vi>& adj, vector<Edge>& E) {
queue<int> Q;
d[t] = 0; Q.push(t);
while (not Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = 0; i < int(adj[u].size()); ++i) {
int e = adj[u][i], v = VEI(u, e);
if (CAP(v, e) > 0 and d[v] == -1) {
d[v] = d[u] + 1;
Q.push(v);
}
}
}
return d[s] >= 0;
}

ll dfs(int u,int t,ll bot,vector<vi>& adj,vector<Edge>& E) {
if (u == t) return bot;
for (; act[u] < int(adj[u].size()); ++act[u]) {
if (CAP(u, e) > 0 and d[u] == d[VEI(u, e)] + 1) {
if (inc) {
return inc;
}
}
}
return 0;
}

ll maxflow(int s, int t, vector<vi>& adj, vector<Edge>& E) {
for (int i=0; i<int(E.size()); ++i) E[i].flow = 0;
ll flow = 0, bot;
while (bfs(s, t, adj, E)) {
while ((bot = dfs(s,t,INF, adj, E))) flow += bot;
}
return flow;
}