网络流之前一直尝试去学过好多次，但一直都没搞懂。
最近一鼓作气终于会最大流的（fuck）
其实有些时候可能真的一瞬间就理解了些东西（上语文课的时候突然理解增广路了）
也推荐一些学习的博客（我们不生产资料，我们只是资料的搬运工）：
关于网络流十分形象的解读以及一些基本概念：http://blog.csdn.net/txl199106/article/details/64441994
关于EK及原理的解释（图很多，虽然有了Dinic要EK也没什么用）：https://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html
Dinic（讲的很好，结构很好，总之很好）：https://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html
因为我太弱，搞不来图片，用画图又太丑。
只能草率的讲一讲思想（个人理解）
EK:虽然没什么用，但复杂度还可以接受。
1.在残量网络中找到一条从S到T的增广路，如果没有则结束该算法。
2.更新这条路上的边，正向边减，反向边加上最小值即可。
3.重复1,2
其实EK还是很简单的，主要是看代码理解一下：
inline int BFS(int s,int t) {memset(pre,-1,sizeof(pre));memset(f,0,sizeof(f));int H=0,T=1;q[1]=s; pre[s]=0; f[s]=1e9;while (H<T){int now=q[++H];for (int i=1;i<=n;++i)if (i!=pre[now]&&pre[i]==-1&&c[now][i]>0){pre[i]=now;f[i]=f[now]<c[now][i]?f[now]:c[now][i];q[++T]=i;}}return f[t]?f[t]:-1; } inline int max_flow(int s,int t) {memset(f,0,sizeof(f));int sum=0,inc;while ((inc=BFS(s,t))!=-1){int now=t;while (now!=s){c[pre[now]][now]-=inc;c[now][pre[now]]+=inc;now=pre[now];}sum+=inc;}return sum; }
Dinic：非常好用的网络流算法，能解决几乎全部的网络流问题。
同EK相似，只不过加上了分层图的一些概念。
1.对整张图跑一遍BFS，记录每个点被访问的深度。
2.通过DFS来找增广路，必须满足被扩展节点的深度为扩展节点深度+1。
3.重复1,2。
主要细节有几个：
1.建边时从0开始编号，每次建两条（一正一反），这样对于每条边i它的反向边就是i^1
2.如果在DFS时经过一个点已经没有增广路了，那么以后经过该点肯定也没有了。因此直接把深度清零即可。
3.DFS时最好一次找多条增广路，可以加快速度。
具体看代码：
inline bool BFS() {memset(dep,0,sizeof(dep));dep[s]=1; q[1]=s;int H=0,T=1;while (H<T){int now=q[++H];for (int i=head[now];i!=-1;i=e[i].next)if (!dep[e[i].to]&&e[i].c){dep[e[i].to]=dep[now]+1;q[++T]=e[i].to;}}return dep[t]; } inline int DFS(int now,int dist) {if (now==t) return dist;int res=0;for (int i=head[now];i!=-1&&dist;i=e[i].next)if (dep[e[i].to]==dep[now]+1&&e[i].c){int dis=DFS(e[i].to,min(dist,e[i].c));dist-=dis; res+=dis;e[i].c-=dis; e[i^1].c+=dis;}if (!res) dep[now]=0;return res; } inline int Dinic() {int sum=0;while (BFS()) sum+=DFS(s,INF);return sum; }
其实网络流难在建模，但要把板子打熟也是很重要的。