初学网络流
这个主题以前没接触过，觉得有点抽象，算法有点不太清楚，看了一些博客，下面，对这些博客做些总结。
引入：
具体参考这篇博客的背景知识讲解部分（具体到代码之前），首先对网络流有了一个初步的印象
https://blog.csdn.net/wzw1376124061/article/details/55001639
然后一些概念性的定义，具体参考这篇博客，对一些可能会影响到算法理解的基础概念进行掌握
https://www.cnblogs.com/widerg/p/9387909.html
算法：
然后接触到算法，显示FF(Ford-Fulkerson)算法的思想，用的是dfs,主要理解增加的反向边和算法的流程。然后是EK算法，也是上面一篇博客
对算法大致了解后可以看看实例，上面一篇博客的图是个理解负向边很好的例子，加上这篇博客
https://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html结合算法对实例的分析
代码：
下面就可以看代码了，主要是这几篇博客比较清晰：
https://blog.csdn.net/wzw1376124061/article/details/55001639
https://www.cnblogs.com/widerg/p/9387909.html
总结与拓展：
最后的总结这篇博客更适合：https://www.cnblogs.com/rvalue/p/10650849.html，分析的比较细，虽然我还不太真正的明白在讲些什么，但估计熟悉以后就会明白了吧
如果还想更高级的dinic算法，也是上一篇博客，加上这个https://baijiahao.baidu.com/s?id=1612179096991409044&wfr=spider&for=pc，讲解的比较清楚
模板：
//Edmonds Karp
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define maxn 1005
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct EdmondsKarp
{
int n,m;
vector<Edge> edges;//保存各个边的信息，包括反向边
vector<int> G[maxn];//G[i][j]表示第i个节点的第j条边在edges中的编号
int a[maxn];//起点到i的可改进量
int p[maxn];//最短路树p的入弧编号
void init(int n)
{
for(int i = 0;i<n;i++)
{
G[i].clear();
}
edges.clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,0));//edges中的第m-2号边，目前的倒数第二个
edges.push_back(Edge(to,from,0,0));//反向边,edges中的第m-1号边,目前的最后一个
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
int Maxflow(int s,int t)
{
int flow = 0;
for(;;)
{
memset(a,0,sizeof(a));
queue<int> que;
que.push(s);
a[s]=INF;
while(!que.empty())
{
int x = que.front();
que.pop();
for(int i = 0;i<G[i].size();i++)
{
Edge& e = edges[G[x][i]];
if(!a[e.to]&&e.cap>e.flow)//如果e.to节点还没有加过流（这一次BFS）
{
p[e.to] = G[x][i];
a[e.to] = min(a[x],e.cap-e.flow);
que.push(e.to);
}
}
if(a[t]) break;//若已拓展到t点，跳出
}
if(!a[t])//若无法到达a点，说明无增广路，结束算法
for(int u = t;u!=s;u=edges[p[u]].from)//从t开始向前更新路径上的流
{
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];//亦或是相反边的编号
}
flow += a[t];
}
return flow;
}
};
//Ford Fulkerson
#include <iostream>
#include <vector>
#include <memory.h>
#define maxn 1005
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int to;//终点
int cap;//容量
int rev;//反向边号
};
vector<edge> G[maxn];//图的邻接表表示
bool used[maxn];//DFS中用到的访问标记
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});//记录反向边在to个节点的vector中的位置
G[to].push_back((edge){from,0,G[from].size()-1});
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
used[v]=1;
for(int i = 0;i<G[v].size();i++)
{
edge& e = G[v][i];
if(!used[e.to]&&0<e.cap)
{
int d = dfs(e.to,t,min(e.cap,f));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;//未找到增广路
}
int max_flow(int s,int t)
{
int flow = 0;
for(;;)
{
memset(used,0,sizeof(used));
int f = dfs(s,t,INF);
if(f==0)
{
return flow;
}
flow += f;
}
}
//Dinic
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define maxn 1005
using namespace std;
struct edge
{
int to;
int cap;
int rev;
};
vector<edge> G[maxn];//图的邻接表表示
int level[maxn];//顶点到原点的距离标号
int iter[maxn];//当前弧，在之前的变已经没有用了
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
//通过BFS寻找从原点出发的且未满流的距离标号
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s] = 0;
que.push(s);
while(!que.empty())
{
int v = que.front();
que.pop();
for(int i = 0;i<G[v].size();i++)
{
edge& e = G[v][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to] = level[v]+1;
que.push(e.to);
}
}
}
}
//通过dfs寻找增广路
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int& i = iter[v];i<G[v].size();i++)
{//当前弧优化，iter[v]的值在随着i改变
edge& e = G[v][i];
if(e.cap>0&&level[v]<level[e.to])
{
int d = dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;//找不到增广路
}
以上模板的表示方式都不太一样，理解后可方便自己选择
参考文章：
以上。