First problem to learn Max Flow.
Ford-Fulkerson is a group of algorithms - Dinic is one of it.
It is an iterative process: we use BFS to check augament-ability, and use DFS to augment it.Here is the code with my comments from its tutorial
#include#include #include #include #include #include #include #include using namespace std;/** Graph Model*/const int MAXA = 400005;const int MAXV = 1005;int A, V, source, dest;// index based loggingint cap[MAXA], flow[MAXA], ady[MAXA], nexts[MAXA], last[MAXV]; int now[MAXA], level[MAXV];void ADD(int u, int v, int c) // from u to v with cap c{ // + edge cap[A] = c; flow[A] = 0; ady[A] = v; nexts[A] = last[u]; last[u] = A++; // - edge cap[A] = 0; flow[A] = 0; ady[A] = u; nexts[A] = last[v]; last[v] = A++;}/** Dinic Algorithm*/bool BFS(int source, int dest){ memset(level, -1, sizeof(level)); level[source] = 0; queue q; q.push(source); while (!q.empty() && level[dest] == -1) { int u = q.front(); q.pop(); // from for (int i = last[u]; i != -1; i = nexts[i]) { int v = ady[i]; // to if (level[v] == -1 && flow[i] < cap[i]) { level[v] = level[u] + 1; // mark level q.push(v); } } } return level[dest] != -1;}int DFS(int u, int aux){ if (u == dest) return aux; for (int i = now[u]; i != -1; now[u] = i = nexts[i]) { int v = ady[i]; // next aux-able level node if (level[v] > level[u] && flow[i] < cap[i]) { int ret = DFS(v, min(aux, cap[i] - flow[i])); if (ret > 0) { flow[i] += ret; // + edge flow[i ^ 1] -= ret;// - edge return ret; } } } return 0;}long long Dinic(){ long long flow = 0, aum; while (BFS(source, dest)) { for (int i = 0; i <= V; i++) now[i] = last[i]; while ((aum = DFS(source, INT_MAX)) > 0) flow += aum; } return flow;}/***/int main(){ // [index]: first n is cluster, next m is wizard.. memset(last, -1, sizeof(last)); int n, m, v, cc; cin >> n >> m; source = 0; V = dest = n + m + 1; // 1. Source -> Cluster with No. with people // Cluster -> Dest with cap of 1 - means no transform // no. of people of each skill for (int i = 1; i <= n; i++) { cin >> v; if (v) ADD(source, i, v); ADD(i, dest, 1); // a non-transformed edge } // wizard info for (int i = 1; i <= m; i++) // m wizards { // array A - index of from-skill cin >> cc; for (int j = 0; j < cc; j++) { cin >> v; ADD(v, n + i, 1); // skill[v](from) -> wizard[i] } // array B - index of to-skill cin >> cc; for (int j = 0; j < cc; j++) { cin >> v; ADD(n + i, v, 1); // wizard[i] -> skill[v](to) } } cout << Dinic() << endl; return 0;}