copy-pasta/maxFlow.cpp
// find augmenting path; augment and update graph; return how much was augmented

find augmenting path; augment and update graph; return how much was augmented
find augmenting path ; augment and update graph ; return how much was augmented
int augmentingPath(Node* source, Node* target)
{
    auto visited = vector<bool>(numNodes, false);
    auto prev = vector<Edge*>(numNodes);
    prev[target->id] = nullptr;
    prev[source->id] = nullptr;
    vector<Node*> Q;
    int front = 0;
    Q.push_back(source);
    visited[source->id] = true;
    bool found = false;
    while(front!=Q.size())
    {
        Node* current = Q[front++];
        for(Edge* edge : current->outgoingEdges)
        {
            if(!visited[edge->to->id] && !(edge->capacity == edge->flow))
            {
                Q.push_back(edge->to);
                prev[edge->to->id] = edge;
                visited[edge->to->id] = true;
                if(edge->to == target)
                {
                    found = true;
                    break;
                }
            }
        }
        if(found) break;
    }
    vector<Edge*> path;
    int pathCapacity = 100000;
    Edge* edge = prev[target->id];
    if(edge == nullptr)
        return 0;
    while(edge != nullptr)
    {
        path.push_back(edge);
        pathCapacity = min(pathCapacity, edge->capacity - edge->flow);
        edge = prev[edge->from->id];
    }
    for(Edge* edge : path)
    {
        edge->flow += pathCapacity;
        if(edge->isResidual)
        {
            edge->twin->flow -= pathCapacity;
        }
        else
        {
            edge->twin->capacity = edge->flow;
        }
    }
    return pathCapacity;
}
int augmentingPath ( Node * source , Node * target ) { auto visited = vector < bool > ( numNodes , false ) ; auto prev = vector < Edge * > ( numNodes ) ; prev [ target -> id ] = nullptr ; prev [ source -> id ] = nullptr ; vector < Node * > Q ; int front = 0 ; Q . push_back ( source ) ; visited [ source -> id ] = true ; bool found = false ; while ( front != Q . size ( ) ) { Node * current = Q [ front ++ ] ; for ( Edge * edge : current -> outgoingEdges ) { if ( ! visited [ edge -> to -> id ] && ! ( edge -> capacity == edge -> flow ) ) { Q . push_back ( edge -> to ) ; prev [ edge -> to -> id ] = edge ; visited [ edge -> to -> id ] = true ; if ( edge -> to == target ) { found = true ; break ; } } } if ( found ) break ; } vector < Edge * > path ; int pathCapacity = 100000 ; Edge * edge = prev [ target -> id ] ; if ( edge == nullptr ) return 0 ; while ( edge != nullptr ) { path . push_back ( edge ) ; pathCapacity = min ( pathCapacity , edge -> capacity - edge -> flow ) ; edge = prev [ edge -> from -> id ] ; } for ( Edge * edge : path ) { edge -> flow += pathCapacity ; if ( edge -> isResidual ) { edge -> twin -> flow -= pathCapacity ; } else { edge -> twin -> capacity = edge -> flow ; } } return pathCapacity ; }
find augmenting path; augment and update graph; return how much was augmented
find augmenting path ; augment and update graph ; return how much was augmented
// vector and start pointer is more efficient than a real queue
 //already seen this node
 //break if target was found
 //augment path by pathcapacity
