简单最大流算法-EK (1)最短

基础的最大流算法，每次Bfs寻找最短路进行增广，这时候的增广和匈牙利算法的增广不同，找出一条残余路径就可以了。

然后对残余网络进行增广，不要忘记正向增广，相当于负向减少，也要在图中保存记录。

最后求一个割集来得到最大流。

 

最大流模型：

点：对点来说要求是进多少出多少

边：对边要求是不能超过最大容量，所以c的值为所有的残余边中的最小值

 

效率

O(VE2)，效率可以满足一般题目要求。

 

模板如下;图保存为邻接阵

typedef int Graph[200][200];
typedef int Path[200];
Graph map,flow;
int n,s,t;
int EK()
{
    int i, j, k=0, c, head, tail; Graph R;        
    Path prev, visit, Q;  
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            flow[i][j] = 0;
            R[i][j] = map[i][j];
        }
    }
    while (true)
    {
        head = tail = 0;
        memset(visit, false, sizeof(visit));
        Q[tail++] = s;
        prev[s]   = -1;
        visit[s]  = 1;
        while (head < tail) {
            k = Q[head++];              
            for (i = 0; i < n; i++)
            {
                if (!visit[i] && R[k][i] > 0)
                {
                    visit[i] = 1;
                    prev[i]  = k;
                    if (i == t) break;
                    if(tail>=0) Q[tail++] = i;
                }
            }
            if(i==t) break;
        }
         if (!visit[t]) break;
        c = 1000000;
        j = t;
        while (j != s) {
            i = prev[j];
            if(c>R[i][j]) c=R[i][j];
            j = i;
        }
        j = t;
        while (j != s)
        {
            i = prev[j];
            flow[i][j] = flow[i][j] + c;
            flow[j][i] = -flow[i][j];
            R[i][j] = map[i][j] - flow[i][j];
            R[j][i] = map[j][i] - flow[j][i];  
            j = i;
        }
     }
    c = 0;
    for (i = 0; i < n; i++) {
        c += flow[s][i];
    }
    return c;
}