由于本人太弱，可能讲解有误，请读者指出。
什么是网络流
网络流是通过构建从源点到汇点的有向图模型来解决图论问题。从理论上讲，网络流可以处理所有二分图问题。
二分图和网络流的难度都在于问题建模，一般不会特意去卡算法效率，所以只需要背一两个简单算法的模板就能应付大部分题目了。
最大流问题什么是最大流例题
P3376 【模板】网络最大流
解释例题
将一些物品从结点 \(s\) 运输到结点 \(t\)，其中可以通过其他的结点中转，每条边都有一条运输物品上限，求最多有多少物品可以从结点 \(s\) 运输到结点 \(t\)。
概念
源点：即结点 \(s\)，出发点。
汇点：即结点 \(t\)，结束点。
容量：记 \(c(u,v)\)，从结点 \(u\) 到结点 \(v\) 的边的运输物品数量上限，若结点 \(u\) 与结点 \(v\) 之间不存在边，\(c(u,v)=0\)。
流量：记 \(f(u,v)\)，从结点 \(u\) 到结点 \(v\) 的边实际运输物品数量。
残量：每条边的容量与流量之差。
由于若将物品从结点 \(u\) 运输到结点 \(v\)，再又将物品运回来是没有任何意义的，所以可以规定 \(f(u,v)=-f(v,u)\)。
如图：每个边上第一个数是流量，第二个数是容量
性质
通过这些概念，我们就可以从中挖掘出一些性质：
- 容量限制：\(f(u,v)\le c(u,v)\)。
- 斜对称性：\(f(u,v)=-f(v,u)\)。
- 流量平衡：\(\sum\limits_{u\ne\{s,t\},(u,v)\in E}f(u,v)=0\)。
这是最大流的重要性质，同时也是它的条件。
增广路算法
增广路算法思想很简单：从零流开始不断的增加流量，每一次增加要保持三条性质就行了。
我们通过每一条边的残量建边，对对原有边建立反向边，得到一个残量网络，注意这里边的数量可能达到原图的两倍：
这样，我们只需要基于这样的事实：残量网络中的任何一条 \(s\) 到 \(t\) 的有向道路都对应着一条原图中的增广路。只需要求出该道路中的所有残量最小值 \(d\)，把所对应的所有边上的流量增加 \(d\) 即可，这个过程就叫增广。如图，红色的就是一条增广路。
不难验证在增广之后它还是满足三条性质的。
如果当图中不存在增广路时，就说明当前流就是最大流了。
这就是增广路定理。
实现——Edmonds-Karp 算法
对于查找路径，我们可以选用 DFS 或 BFS，但是如果用 DFS 则一不小心就会超时，所以应该选用 BFS来实现，时间复杂度 \(O(nm^2)\)。
Code
int Bfs() { memset(pre, -1, sizeof(pre)); for(int i = 1 ; i <= n ; ++ i) flow[i] = INF; queue q; pre[S] = 0, q.push(S); while(!q.empty()) { int op = q.front(); q.pop(); for(int i = 1 ; i <= n ; ++ i) { if(i==S||pre[i]!=-1||c[op][i]==0) continue; pre[i] = op; //找到未遍历过的点 flow[i] = min(flow[op], c[op][i]); // 更新路径上的最小值 q.push(i); } } if(flow[T]==INF)return -1; return flow[T];}int Solve() { int ans = 0; while(true) { int k = Bfs(); if(k==-1) break; ans += k; int nw = T; while(nw!=S) {//更新残余网络 c[pre[nw]][nw] -= k; c[nw][pre[nw]] += k; nw = pre[nw]; } } return ans;}Dinic 算法
Edmonds-Karp 算法的劣势就在于，每次遍历了一遍残量网络之后只能求出一条增广路来增广。
于是我们针对这一点进行优化，我们就得到了一个更加优秀的替代品，Dinic 算法。
Dinic 算法的关键就是分层图和阻塞流。
分层图
分层图就是按照结点 \(s\) 到另一个点的最短距离进行分层，相同距离分到一层，就像 \(s\to 第一层\to 第二层\to 第三层\cdots\)。这样就可以得到每一条这样的路径都是 \(s-t\) 最短路。
阻塞流
阻塞流就是指不考虑反向边的“极大流”。每一次增广路后将路径上最小的流量增广，但是减小，再将那条边阻塞。
这就是三次增广后的结果，当图中不存在 \(s-t\) 路径，是增广结束，这就是阻塞流。
时间复杂度
由于最多进行 \(n-1\) 次阻塞流，每次计算不超过 \(O(nm)\)，看上去是总时间复杂度是 \(O(n^2m)\)，但如果是对于二分图最大匹配这样的图，时间复杂度只有 \(O(n^{\frac{1}{2}}m)\)。
Code
struct edge{ int to, value, net;} e[N << 1]; //共有n*2条边void add(int from, int to, int value){ //链式前向星 cnt++; e[cnt].to = to; e[cnt].value = value; e[cnt].net = head[from]; head[from] = cnt;}int bfs(int st, int ed){ //建立层次图 queue que; memset(dis, -1, sizeof(dis)); dis[st] = 0; que.push(st); while (!que.empty()){ int x = que.front(); que.pop(); for (int i = head[x]; i > -1; i = e[i].net){ int now = e[i].to; if (dis[now] == -1 && e[i].value){ que.push(now); dis[now] = dis[x] + 1; } } } return dis[ed] != -1;}int dfs(int x, int t, int maxflow){ if (x == t) return maxflow; int ans = 0; for (int i = cur[x]; i > -1; i = e[i].net){ ///当前弧优化 int now = e[i].to; if (dis[now] != dis[x] + 1 || e[i].value == 0 || ans >= maxflow) continue; cur[x] = i; int f = dfs(now, t, min(e[i].value, maxflow - ans)); e[i].value -= f; e[i ^ 1].value += f; //反向边加流量 ans += f; } if(!ans)dis[x] = -1; return ans;}int Dinic(int st, int ed){ int ans = 0; while (bfs(st, ed)){ memcpy(cur, head, sizeof(head)); int k; while ((k = dfs(st, ed, INF))) ans += k; } return ans;}