学习地方：
EK模板:O(V*E^2)
临街矩阵实现：
int bfs(int s,int e){ int i; queue q; CL(vt,false); CL(pre,-1);//初始化 for (i = 0; i <= n + 1; ++i) f[i] = inf;//注意这里的范围 q.push(s); vt[s] = true; while (!q.empty()){ int u = q.front(); q.pop(); for (i = 0; i <= n + 1; ++i){ //如果回到父亲节点，或者该点已经被访问过，或者这条路不满足有流量 if (i == u || vt[i] || pre[i] != -1 || mp[u][i] <= 0) continue; vt[i] = true; f[i] = min(f[u],mp[u][i]);//选出该路径上的最小流量 pre[i] = u;//记录i的父亲为u q.push(i); if (i == e){ flag = true; break; } } if (flag) break; } if (f[e] == inf) return -1; else return f[e];}int EK(int s,int e){ int i; int ans = 0; while (1){ flag = false; int d = bfs(s,e);//寻找可行流 if (d == -1) break; //更新流量 for (i = e; i != s; i = pre[i]){ int u = pre[i]; mp[u][i] -= d; mp[i][u] += d; } ans += d; } return ans;}
邻接表实现：
struct node{ int v,w; int next;}g[M*4 + 10];int head[N],ct;void init(){ ct = 0; CL(head,-1);}void add(int u,int v,int w){ g[ct].v = v; g[ct].w = w; g[ct].next = head[u]; head[u] = ct++; g[ct].v = u; g[ct].w = 0; g[ct].next = head[v]; head[v] = ct++;}int bfs(int s,int e){ int i; for (i = 0; i <= n; ++i) f[i] = inf; CL(vt,false); CL(pre,-1); CL(path,-1); queue q; q.push(s); vt[s] = true; while (!q.empty()){ int u = q.front(); q.pop(); for (i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if (vt[v] || g[i].w <= 0 || pre[g[i].v] != -1) continue; pre[v] = u; path[v] = i; vt[v] = true;//多了一个path记录可行流这条路上的路的编号 f[v] = min(f[u],g[i].w); if (v == e) break; q.push(v); } } if (f[e] == inf) return -1; else return f[e];}int EK(int s,int e){ int i,ans = 0; while (1){ int d = bfs(s,e); if (d == -1) break; int tp; for (i = e; i != s; i = pre[i]){ tp = path[i];//去路径编号 g[tp].w -= d; g[tp^1].w += d; } ans += d; } return ans;}还有一种写法就是记录逆向边，这里不用记录们因为当前变与逆变abs（差值）= 1，取抑或即可。另一种写法http://blog.sina.com.cn/s/blog_6635898a0100ly53.html
Dinic模板：
邻接表实现：
struct node{ int v,w; int next;}g[M*4 + 10];int head[N],ct;void init(){ ct = 0; CL(head,-1);}void add(int u,int v,int w){ g[ct].v = v; g[ct].w = w; g[ct].next = head[u]; head[u] = ct++; g[ct].v = u; g[ct].w = 0; g[ct].next = head[v]; head[v] = ct++;}//分层bool layer(int s,int e){ int i; CL(level,-1); level[s] = 0; int l,r; l = r = 0; q[r] = s; while (l <= r){ int u = q[l++]; for (i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if (level[v] == -1 && g[i].w > 0){ level[v] = level[u] + 1; q[++r] = v; if (v == e) return true; } } } return false;}int find(int s,int e){ int i; int ans = 0; int top = 1; while (top){ int u = (top == 1 ? s : g[q[top - 1]].v);//如果没有变肯定是起点，否则就是上一个边终点 if (u == e){ int MIN = inf,pos; //找出最小流量 for (i = 1; i < top; ++i){ int tp = q[i];//注意这里取边的编号 if (g[tp].w < MIN){ MIN = g[tp].w; pos = i; } } //更新容量 for (i = 1; i < top; ++i){ int tp = q[i];//注意这里取边的编号 g[tp].w -= MIN; g[tp^1].w += MIN; } ans += MIN; top = pos; } else{//找可行流 for (i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if (g[i].w > 0 && level[v] == level[u] + 1){ q[top++] = i; break; } } if (i == -1){//如果u没有可走的子节点 top--; level[u] = -1; } } } return ans;}int Dinic(int s,int e){ int ans = 0; while (layer(s,e)) ans += find(s,e);//分层成功找可行流 return ans;}
上边的Dinic在写最大权闭合图时，超时，后来又搜了一个新模板：
bool layer(int s,int e){ int i; CL(level,-1); level[s] = 0; int l = 0, r= 0; q[r] = s; while (l <= r){ int u = q[l++]; for (i = head[u]; i != -1; i = g[i].next) { int v = g[i].v; if (level[v] == -1 && g[i].w > 0) { level[v] = level[u] + 1; q[++r] = v; if (v == e) return true; } } } return false;}ll dinic(int s,int e){ ll ans = 0; while (layer(s,e)) { int top = 0,u = s,i; for (i = s; i <= e; ++i) out[i] = head[i]; while (out[s] != -1) { if (u == e) { ll MIN = inf; for (i = top - 1; i >= 0; --i) { MIN = min(MIN,g[q[i]].w); } for (i = top - 1; i >= 0; --i) { g[q[i]].w -= MIN; g[q[i]^1].w += MIN; if (g[q[i]].w == 0) top = i; } ans += MIN; u = g[q[top]].u; } else if (out[u] != -1 && g[out[u]].w > 0 && level[u] + 1 == level[g[out[u]].v]) { q[top++] = out[u]; u = g[out[u]].v; } else { while (top > 0 && u != s && out[u] == -1) u = g[q[--top]].u; out[u] = g[out[u]].next; } } } return ans;}