Network Flow Template (SAP)

This algorithm was named for Shortest Augmenting Path (SAP).. From an OIer, at about year 2010.

Introduction

Total of n nodes, m edges.
S is source node means 'source'.
T is sink node means 'target'.
maxsap is the maximum height mark, if h[S]==maxsap means there's no path from S to T.
(Array)h[n] is represented for the height of the Node.
(Array)nh[n] : the count of h, e.g. nh[5]=9 means that there have 9 nodes i was satisfied with h[i]==5;

Time complexity : worst-case O(EV²) (m:Edge n:Vertix)

Code

/*
Array g is a pool to save all of edge, the variable eptr shows that how many resource has been used.
*/
struct Edge {
    int to;
    long long flow;
    Edge *next, *pair;
}g[MAXM],*head[MAXN];
int eptr=0;
Edge* _addedge(int a, int b, long long f) {
    g[eptr].to = b; g[eptr].flow = f;
    g[eptr].next = head[a]; head[a] = &g[eptr];
    return &g[eptr++];
}
void addEdge (int a, int b, long long f) {
    Edge* t1=_addedge(a,b,f);
    Edge* t2=_addedge(b,a,0);
    t1->pair=t2; t2->pair=t1;
}

int S,T,maxsap;
int h[MAXN],nh[MAXN];
/*
p is Node,
low means that how many 'flow' push into this node p.
*/
int sap(int p, int low) {
    if (p==T)
        return low;
    int left=low, hmin=maxsap;
    for (Edge *e=head[p]; e; e=e->next) {
        if (e->flow>0 && h[p]==h[e->to]+1) {
            int tt=sap(e->to, min(e->flow,left));
            e->flow-=tt; e->pair->flow+=tt;
            left-=tt;
            if (!left || h[S]==maxsap)
                return low-left;
        }
        if (e->flow>0 && hmin>h[e->to]+1)
            hmin = h[e->to]+1;
    }
    if (low==left) {
        if (! --nh[h[p]])
            h[S]=maxsap;
        else
            ++nh[ h[p]=hmin ];
    }
    return low-left;
}

int main() {
    for (....)
        addEdge(nodeA, nodeB, flowAB);
    int ans=0;
    while (h[S]<maxsap)
        ans += sap(S,INF);
    cout<<ans<<endl;
}