P3376 【模板】网络最大流
大意
求最大网络流。
思路
这里给出两种实现形式。
首先是 EK，这种方式是通过不断的 bfs 去求出一条 \(S \to T\) 的增广路，显然的事情是，这条边的流量受其 \(c_\min\) 的限制，我们只需要在 bfs 的时候记录一下我们找出来的链，然后去跳这个链，找 \(c_\min\)，然后再跳一遍，进行修改，不断上述的操作，直到找不到增广路。
然后是 Dinic，这个算法的 EK 的优化算法，是利用 DFS 来一次多路增广的，我们只需要将整个图分层，对增广分层后的图进行 DFS 多路增广，更新，直到找不到增广路。
代码
// EK
bool bfs(){queue<int> q;q.push(S);memset(pre, -1, sizeof(pre));while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(pre[v] == -1 && e[i].c){pre[v] = i;if(v == T) return true;q.push(v);}}}return false;
}int EK(){int res = 0;while(bfs()){int Min = 1e9;for(int i = T;i != S;i = e[pre[i]].u){Min = min(Min, e[pre[i]].c);}for(int i = T;i != S;i = e[pre[i]].u){e[pre[i]].c -= Min;e[pre[i] ^ 1].c += Min;}res += Min;}return res;
}//Dinic
bool bfs(){queue<int> q;memset(d, -1, sizeof(d));d[S] = 0;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == -1){d[v] = d[u] + 1;q.push(v);}}}return (d[T] == -1) ? false : true;
}int dfs(int u, int flow){if(u == T){return flow;}int res = 0;for(int &i = cur[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == d[u] + 1){int tmp = dfs(v, min(flow, e[i].c));e[i].c -= tmp;flow -= tmp;e[i ^ 1].c += tmp;res += tmp;if(!flow) break;}}if(!res){d[u] = -1;}return res;
}int Dinic(){int res = 0;while(bfs()){memcpy(cur, h, sizeof(h));res += dfs(S, 1e9);}return res;
}