最大流isap模板

isap+bfs初始化+栈优化，点的编号从0开始：

 const int MAXN = ;

 const int MAXM = ;

 const int INF = 0x3f3f3f3f;

 struct Edge

 {

     int to, next, cap, flow;

 }edge[MAXM];

 int tol;

 int head[MAXN];

 int gap[MAXN], dep[MAXN], cur[MAXN];

 void init()

 {

     tol = ;

     memset(head, -, sizeof(head));

 }

 void addedge(int u, int v, int w, int rw = )

 {

     edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = ;

     edge[tol].next = head[u]; head[u] = tol++;

     edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = ;

     edge[tol].next = head[v]; head[v] = tol++;

 }

 int Q[MAXN];

 void BFS(int start, int end)

 {

     memset(dep, -, sizeof(dep));

     memset(gap, , sizeof(gap));

     gap[] = ;

     int front = , rear = ;

     dep[end] = ;

     Q[rear++] = end;

     while(front != end) {

         int u = Q[front++];

         for(int i = head[u]; i != -; i = edge[i].next) {

             int v = edge[i].to;

             if(dep[v] != -) continue;

             Q[rear++] = v;

             dep[v] = dep[u] + ;

             gap[dep[v]]++;

         }

     }

 }

 int S[MAXN];

 int sap(int start, int end, int N) {  //start是源点编号，end是汇点编号，N是点的总数，返回最大流

     BFS(start, end);

     memcpy(cur, head, sizeof(head));

     int top = ;

     int u = start;

     int ans = ;

     while(dep[start] < N)

     {

         if(u == end)

         {

             int Min = INF;

             int inser;

             for(int i = ; i < top; i++)

                 if(Min > edge[S[i]].cap - edge[S[i]].flow) {

                     Min = edge[S[i]].cap - edge[S[i]].flow;

                     inser = i;

                 }

             for(int i = ; i < top; i++)

             {

                 edge[S[i]].flow += Min;

                 edge[S[i]^].flow -= Min;

             }

             ans += Min;

             top = inser;

             u = edge[S[top]^].to;

             continue;

         }

         bool flag = false;

         int v;

         for(int i = cur[u]; i != -; i = edge[i].next)

         {

             v = edge[i].to;

             if(edge[i].cap - edge[i].flow && dep[v] +  == dep[u])

                 flag = true;

                 cur[u] = i;

                 break;

             }

         }

         if(flag)

         {

             S[top++] = cur[u];

             u = v;

             continue;

         }

         int Min = N;

         for(int i = head[u]; i != -; i = edge[i].next)

             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)

             {

                 Min = dep[edge[i].to];

                 cur[u] = i;

             }

         gap[dep[u]]--;

         if(!gap[dep[u]]) return ans;

         dep[u] = Min + ;

         gap[dep[u]]++;

         if(u != start) u = edge[S[--top]^].to;

     }

     return ans;

 }