最大流EK算法模板（BFS实现）

变量解释：

s-源点

d-汇点

r[i][j]-残留网络中结点i和结点j间的流量，初始值为边<i,j>的容量

flow[i]-记录从源点到结点i的路径<s,...,i>可容纳的最大流量，显然由最短板原理，flow[i]为路径<s,...,i>中容量最少的那一段的容量

pre[i]-记录结点i的前驱结点，以便保存增广路径，同时标记已加入队列的结点，避免重复访问

#define min(x, y) ((x) < (y) ? (x) : (y))

const int maxn = 405;
const int inf = 0x7fffffff;
int r[maxn][maxn];  //记录残留网络的容量 
int flow[maxn];  //标记从源点到当前结点实际还剩多少流量可用
int pre[maxn];  //结点的前驱, 同时标记该节点是否在队列中 
int n, m;

int BFS(int s, int d)  //使用BFS寻找增广路径 
{
    queue<int> que;
    memset(pre, -1, sizeof(pre));
    pre[s] = 0;
    flow[s] = inf;  //初始化源点的流量为无穷大 
    que.push(s);
    while(!que.empty())
    {
        int cur = que.front();
        que.pop();
        for(int i = 1; i <= d; ++i)  //遍历所有的结点 
        {
            //原图是没有流向s的流的，但是在剩余网络中有反向边，故残留图中有到s的流，故须判断i != s,但由于已经设定 pre[s] = 0，故
            //对i != s的判断寓于对pre == -1的判断中
            if(r[cur][i] > 0 && pre[i] == -1)
            {
                 pre[i] = cur;  //记录前驱以保存路径 
                 flow[i] = min(r[cur][i], flow[cur]);   //关键：迭代地找到增量 
                 if(i == d) return flow[d];  //抵达汇点，找到增广路径
                 que.push(i);               
            }
        }
    } 
    return -1;  //没有流能到达d，残留图中不再存在增广路径        
}

int EK(int s,int d)
{
    int inc = 0;
    int max_flow = 0;
    while((inc = BFS(s, d)) != -1)
    {
        for(int i = d; i != s; i = pre[i]) //利用前驱寻找路径
        {
            //以下两步更新残留图
            r[pre[i]][i] -= inc;  //改变正向边的容量
            r[i][pre[i]] += inc;  //改变反向边的容量
        }
        max_flow += inc;
    }   
    return max_flow;
}