最大流：源点到汇点的流量最大
Dinic基本思想：
- bfs广搜实现查找多条增广路（可能可以增加流量的路），构建一张层次图。
- 在bfs找到增广路的前提下多次dfs深搜进行增广直至所有已查找到的增广路用完
优化：当前弧优化：
在每次更新完的层次图中（即每一次bfs完后），dfs每增广完一条路之后，该路的价值就已可以看作用尽了，没有必要在之后的dfs中再次深搜该路。故记录下用完价值的边的下一条边，下一次的dfs直接从该边开始，这样就避免了不必要的增广。
/* 普通图的情况下：复杂度O(V2 E) 二分图下的复杂度：O(根号(VE)) */ #include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; const int maxv = 10004, maxe = 200004; /*cap 为边的容量 */ struct Edge { int next, to, cap; }e[maxe]; int head[maxv], cnte = 1; int level[maxv], cur[maxv]; int n, m; inline bool min(const int& a, const int& b) { return a<b? a:b; } inline void add_edge(int from, int to, int cap) { cnte += 1; e[cnte].next = head[from], e[cnte].to = to, e[cnte].cap = cap; head[from] = cnte; //反向边, 初始的容量为0 cnte += 1; e[cnte].next = head[to], e[cnte].to = from, e[cnte].cap = 0; head[to] = cnte; return; } //bfs分层找增广路，建立层次图 bool bfs(int s, int t) { memset(level, 0, sizeof(level)); queue<int> q; while(q.size()) q.pop(); level[s] = 1; q.push(s); while(q.size()) { int now = q.front(); q.pop(); for(int i=head[now]; i; i=e[i].next) { //有容量且没有被标记 if(level[e[i].to]==0 && e[i].cap > 0) { level[e[i].to] = level[now]+1; q.push(e[i].to); } } } //终点的level大于0说明存在增广路 return level[t] > 0; } //增广流量 //in 为源点输入到这个点上的最小边权 //now 收到的支持，不一定真正能够用到 //@return 真正的输出流量 /** dfs的意义为到达now时传进的最大流量 */ int dfs(int now, int t, int in) { if(!in || now==t) return in; //i为cur[now]的引用-->cur[now]随着i改变 for(int& i=cur[now]; i; i=e[i].next) { int nv = e[i].to; if(level[nv]==level[now]+1 && e[i].cap>0) { // out为点now经边i流向nv的流量 int out = dfs(nv, t, min(in, e[i].cap)); //一路上都受到最小流量的限制 if(out > 0) { e[i].cap -= out; e[i^1].cap += out; //反向边，用于反悔 return out; } } } return 0; //没有增广路，返回0 } //注意是两个while，每次bfs找到多个增广路后 //多次dfs计算网络中所有增广路的流量 int dinic(int s, int t) { int max_flow = 0; while(bfs(s, t)) { //每次建立完层次图之后记录当前弧 for(int i=1; i<=n; ++i) cur[i] = head[i]; int tmp=0; while(tmp = dfs(s, t, 0x3f3f3f3f)) max_flow += tmp; } return max_flow; }