简单最大流算法-EK (2)最大容量找路径代码

#include
using namespace std;
typedef int path[200];
int map[200][200];
int ek(int src,int sink, int n)
{
    int i,j,total;
    if(src == sink)
        return INT_MAX;
    path prev,visit,flow;
    while(true)    
    {
        //去掉所有标记
        for(i=0;i        {
            pre[i]=-1;
            flow[i]=0; //从源点到i最多可以增加的流量
            visit[i] = false;
        }
        flow[src]= INT_MAX;
        //找一条路径
        while(true)
        {
            maxflow =0;
            maxnode=-1;
            //每次都找下一层的最大边
            for(i=0;i                if(flow(i)>maxflow && !visit[i])
                {
                    maxflow = flow[i]; //从src到i的最大增量
                    maxnode = i;
                }
            if(-1 == maxnode || maxnode == sink)
                break;
            visit[maxnode]=true;
            //对maxnode的所有相邻节点作标记,想借此找出此路径上最小的增量,其实可以不标，直接搜一遍这个路径即可,只不过想一遍完而已
            for(j=0;j            {
                if(flow[j] < min(maxflow, map[maxnode][j]) )
                {
                    pre[j]  = maxnode;
                    flow[j] = min(maxflow,map[maxnode][j]); //表明j的增不会超前趋的增
                }
            }
        }
        //寻路结束
        if(maxnode == -1) //no path
            break;
        increment = flow[sink]; //标记法的好处,此路径上从源点到汇点的最大增量
        total+=increment;
        k = sink;
        while(k!=src)
        {
            i = pre[k];
            map[i][k]-=increment;   //更新残余网络
            map[k][i]+=increment;
            k = i;
        }
    }
    return total;
}