最大流dinic算法，模板题
EK算法，每次调用一次 bfs，只能找到一条 增光路。
dinic算法每调用一次 bfs, 就可以找到多条的增光路。
本题要点：
1、dinic 步骤
a) 用bfs建立分层图， 实际是一个增广网
b) 建立一个分层图后，再 dfs 在增广网，计算所有可能的增广路上的流量的总和.
2、dinic 算法的剪枝：当前弧优化：
now 数组，记录每个点将要访问的第一条边。
在bfs建立分层图的时候，某个点 x 第一次入队列, now[x] = head[x]。
在 dfs 的过程中，一次处理的多条增光路，这些增光路可能在某个点相交（假设为x点），
就会多次调用函数 dfs(x, long long sum), 每次从 now[x]中，选择第一条要处理的边。
假设 x点有 y, z, w 三条边， x点的上一点是 fax。第一次进入 dfs(x, sum), 处理了 y 边，剩下 z 和 w 边。
但是此时 边 fax --> x 的流量不足，所以无法处理 z和 w边。 这时候，在for循环内，now[x] = i; //当前弧优化，
也就是把x点的将要处理的第一条边设为 了y边。
for(int i = now[x]; i && sum; i = e[i].next)
{now[x] = i; //当前弧优化...
}
第二次进入点x，调用函数 dfs(x, sum)， 此时的now[x] 指向了y边。
3、dinic 算法的剪枝：去掉增广完毕的点
k = dfs(v, min(sum, e[i].val));
if(k == 0)dis[v] = inf; //剪枝，去掉增广完毕的点
k = dfs(v, min(sum, e[i].val)); k是表示当前走点v，能流过的最大流量是k， 当k == 0， 说明此点走不通，
直接赋值 dis[v] = inf, 后面就不会进入点v，因为不满足分层图的 （u点到v点有 边） d[u] + 1 == d[v] 的要求。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 520010;
const long long inf = 2005020600;
int n, m, s, t, u, v;
long long w, ans, dis[MaxN];
int tot = 1, now[MaxN], head[MaxN];struct node
{
int to, next;long long val;
}e[MaxN];void add(int u, int v, long long w)
{
e[++tot].to = v, e[tot].val = w, e[tot].next = head[u], head[u] = tot;e[++tot].to = u, e[tot].val = 0, e[tot].next = head[v], head[v] = tot;
}bool bfs()
{
for(int i = 1; i <= n; ++i)dis[i] = inf;queue<int> q;q.push(s);dis[s] = 0, now[s] = head[s];while(!q.empty()){
int x = q.front();q.pop();for(int i = head[x]; i; i = e[i].next){
int v = e[i].to;if(e[i].val > 0 && dis[v] == inf){
q.push(v);now[v] = head[v];dis[v] = dis[x] + 1;if(v == t)return true;}}}return false;
}int dfs(int x, long long sum) //sum是整条增广路对最大流的贡献
{
if(x == t)return sum;long long k, res = 0; //k是当前最小的剩余容量for(int i = now[x]; i && sum; i = e[i].next){
now[x] = i; //当前弧优化int v = e[i].to;if(e[i].val > 0 && dis[v] == dis[x] + 1){
k = dfs(v, min(sum, e[i].val));if(k == 0)dis[v] = inf; //剪枝，去掉增广完毕的点 e[i].val -= k;e[i ^ 1].val += k;res += k; //res表示经过该点的所有流量和（相当于流出的总量） sum -= k; //sum表示经过该点的剩余流量}}return res;
}int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);for(int i = 1; i <= m; ++i){
scanf("%d%d%lld", &u, &v, &w);add(u, v, w); }while(bfs()){
ans += dfs(s, inf);}printf("%lld\n", ans);return 0;
}/* 4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40 *//* 50 */