最大流之EK

朴实的最大流算法

int EK(int s,int t)
{
    int inf=0xfffffff ;
    int u,i,flow ;
    int ans=0 ;
    while(1)                                                
    {
        queue <int> q ;                
        memset(vis,0,sizeof(vis)) ;
        memset(pre,0,sizeof(pre)) ;
        vis[s]=1 ;
        q.push(s) ;
        while(!q.empty())
        {      
            u=q.front() ;
            q.pop() ;
            if(u==t)
                break ;
            for(i=1;i<=t;i++)
                if(!vis[i] &&c[u][i])
                {
                    q.push(i) ;
                    pre[i]=u ;
                    vis[i]=1 ;
                }
        }
        if(!vis[t])
            break ;
        flow=inf ;
        for(u=t;u!=s;u=pre[u])
            flow=min(flow,c[pre[u]][u]) ;
        for(u=t;u!=s;u=pre[u])
        {
            c[pre[u]][u]-=flow ;
            c[u][pre[u]]+=flow ;
        }
        ans+=flow ;
    }
    return ans ;
}