序：
在之前的博文中，我解释了关于最大流的EK与Dinic算法，以及它们的STL/非STL的实现（其实没什么区别）。本次讲解的是ISAP算法。‘I’，指 improved，也就是说ISAP其实是SAP算法的改进。目前没有官方名称。

经过测试，ISAP的效率在洛谷的板子题中远胜于EK和Dinic的，速度大概是它们的2-3倍。代码量实际上并没有多大变化，在20行读入优化与不压行的情况下（即下文代码），200-210行。（如果压行的话，120行问题不大。不要问我为什么，我空行太多…如果加读入优化的话，再加上15行）

本文给出三种实现方式：递归，非递归，STL，非STL，将ISAP用结构体封装，直接调用函数（每种包含几个，实际上并没有什么差别）。

温馨提示：
在开启O2优化后，vector+queue版的ISAP比数组模拟的要快一点点（10ms?，运行时间均在90-110ms之间）。
如果不开优化，数组模拟比STL版要快2-3倍，达到120-150ms，而STL版是350-400ms（多次提交测试）。
什么级别的考试用什么，这应该很好取舍。

---

ISAP的思路：
当我们使用Dinic跑最大流的时候，我们多次进行了BFS分层，直到汇点不在残余网络之中。而ISAP则只BFS分层一次（事实上你都甚至可以不进行分层，也就比分层慢一点）。ISAP通过新的方式分层。

对于任意一个节点x，当跑完数次最大流之后，我们发现所有与它相连的节点都不满足level[i]+1 == level[x]了。出现这种情况，Dinic的做法是重新分层，而ISAP的做法是将level[x]置成min(level[i])+1，从而构造出一条可行流。

当然，这是有边界的。我们从汇点开始分层，源点的层数最高是n-1（一条链），所以当level[st] >= n的时候，算法结束，残余网络中一定不存在可行流了。
这种方式也就解释了为什么可以不预先分层。因为这样，分层的工作就留给了每一次推进可行流之中（否则无法找到可行流）。

注：分层时从汇点分层。

但是如果仅仅是这样，实际上快不了多少。

---

真正的优化在于这两个：gap优化和当前弧(cur)优化。

gap优化：
Dinic的反复分层被改成了ISAP的向上构造，而可行流必须满足level[起点] = level[终点]+1，也就是说如果出现了断层，也就是说在某一level的层级中不存在节点，那么就不会再出现可行流(比如这一层是x，那么流无法从lev.(x-1)流到lev.(x+1))，直接结束算法，比不加它的ISAP快到不知哪里去了。

cur优化（当前弧）:
对于任意一个节点x，假设最大流已经经过它流向下一个节点，而后在某次又流到了它(比如说已经找到一条可行流，从源点重新寻找可行流，再次到达该节点)，那么该可行流一定不能再流到之前流过的那些弧了（那些弧已经流过了，再进去相当于又走了一遍老路，但是上一次已经最大化的利用了它的流量限制，也就是说这次是没有任何意义的行为。）
为了避免这种情况，我们用一个数组cur[]来记录每个节点当前流到的弧的编号（这是边表存储的情况。如果是邻接矩阵存储，那就记录当前流到了下一个节点的编号），当下一次又经过该节点的时候，我们只需要再去尝试没有流过的弧了。

举个例子：
节点5有三条弧，分别是arc1,arc2,arc3 。在之前寻找可行流的过程中，经过了arc1。那么将cur[5] = arc2，下一次便从arc2开始寻找可行流。

可能会有这样一个问题：
凭什么就说arc1就没有再走的价值了，那如果上一次通过arc1流向了节点6，而可行流最终是通过节点6的某一条弧流向汇点的，但是节点6不一定只有一条弧啊，下一次还可以走节点6的其他弧。

解释也很简单，这是递归的过程，如果流已经流回到了节点5，那么说明节点6以及arc1所抵达的所有节点都已经进行了这项操作。

当然，如果出现对某结点重新分层的时候，要将该节点的cur置回0（因为当前已经到尾了）。

---

代码实现：
1.STL+DFS+非结构体版：

/*

About: Max_flow ISAP STL+DFS

Auther: kongse_qi

Date: 2017/04/30

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <ctype.h>

#include <queue>

#define maxn 10005

#define maxm 200005

#define INF 0x3f3f3f

#define read(x) Get_Int(), x = in

#define p_b(x) push_back(x)

using namespace std;

struct Edge{

    int st, en, weight;

    Edge(){}

    Edge(int s, int e, int w):

        st(s), en(e), weight(w){}

}edge[maxm];

vector<int> arc[maxn];

typedef vector<int>::iterator iterator_t;

int n, m, st, en, tot;

int max_flow;

int num[maxn];

int dis[maxn];

int cur[maxn];

int pre[maxn];

char *X, *Buffer, c;

int in;

void Get_All()

{

    fseek(stdin, 0, SEEK_END);

    int file_lenth = ftell(stdin);

    rewind(stdin);

    Buffer = (char*)malloc(file_lenth*sizeof(char));

    fread(Buffer, 1, file_lenth, stdin);

    X = Buffer;

    c = *X;

    return ;

}

void Get_Int()

{

    in = 0;

    while(!isdigit(c))  c = *++X;

    while(isdigit(c))

    {

        in = in*10+c-'0';

        c = *++X;

    }

    return ;

}

void Init()

{

    //freopen("test.in", "r", stdin);

    Get_All();

    tot = -1;

    read(n), read(m);

    read(st), read(en);

    int a, b, c;

    for(int i = 0; i != m; ++i)

    {

        read(a), read(b), read(c);

        edge[++tot] = Edge(a, b, c);

        edge[++tot] = Edge(b, a, 0);

        arc[a].p_b(tot-1);

        arc[b].p_b(tot);

    }

    return ;

}

bool Bfs()

{

    bool wh[maxn];

    memset(wh, 0, sizeof wh);

    queue<int> q;

    q.push(en);

    wh[en] = true;

    while(!q.empty())

    {

        int cur = q.front(); q.pop();

        for(iterator_t i = arc[cur].begin(); i != arc[cur].end(); ++i)

        {

            Edge& ne = edge[*i];

            if(wh[ne.en] == false)

            {

                dis[ne.en] = dis[cur]+1;

                q.push(ne.en);

                wh[ne.en] = true;

            }

        }

    }

    if(wh[st] == false) return false;

    return true;

}

int Augment(int x)

{

    int minn = INF;

    while(x != st)

    {

        Edge& e = edge[pre[x]];

        minn = min(minn, e.weight);

        x = e.st;

    }

    x = en;

    while(x != st)

    {

        int curr = pre[x];

        edge[curr].weight -= minn;

        edge[curr^1].weight += minn;

        x = edge[curr].st;

    }

    return minn;

}

void Advance(int x)

{

    bool wh = false;

    for(int& i = cur[x]; i != arc[x].size(); ++i)

    {

        Edge& e = edge[arc[x][i]];

        if(e.weight > 0 && dis[x] == dis[e.en]+1)

        {

            wh = true;

            pre[e.en] = arc[x][i];

            x = e.en;

            break;

        }

    }

    if(wh == false)

    {

        int m = n-1;

        for(iterator_t i = arc[x].begin(); i != arc[x].end(); ++i)

        {

            Edge& e = edge[*i];

            if(e.weight > 0)

            {

                m = min(m, dis[e.en]);

            }

        }

        if(--num[dis[x]] == 0)  return ;

        ++num[dis[x] = m+1];

        cur[x] = 0;

        if(x != st) x = edge[pre[x]].st;

    }

    if(x == en)

    {

        max_flow += Augment(en);

        x = st;

    }

    if(dis[st] >= n)    return ;

    Advance(x);

    return ;

}

int Isap()

{

    if(Bfs())

    {

        for(int i = 1; i != n+1; ++i)

        {

            ++num[dis[i]];

        }

        Advance(st);

    }

    else return -1;

    return max_flow;

}

int main()

{

    Init();

    printf("%d\n", Isap());

    return 0;

}

2.struct+非STL+BFS版 (不开O2它最快)

/*

About: Max_flow ISAP struct 非STL+BFS

Auther: kongse_qi

Date: 2017/04/30

*/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <ctype.h>

#define maxn 10005

#define maxm 200005

#define INF 0x3f3f3f

#define read(x) Get_Int(), x = in

using namespace std;

void Get_Int();

void Get_All();

char *X, *Buffer, c;

int in;

struct Edge{

    int st, en, weight;

    Edge(){}

    Edge(int s, int e, int w):

        st(s), en(e), weight(w){}

};

struct Isap{

    int st, en, tot, n, m;

    int max_flow;

    int num[maxn];

    int dis[maxn];

    int cur[maxn];

    int pre[maxn];

    int arc[maxn][maxn/50];

    int amount[maxn];

    Edge edge[maxm];

    void Init(int st, int en, int n, int m)

    {

        tot = -1;

        this -> st = st; this -> en = en;

        this -> n = n; this -> m = m;

        max_flow = 0;

        memset(cur, 0, sizeof cur);

        memset(num, 0, sizeof num);

        memset(amount, -1, sizeof amount);

        return ;

    }

    void Add_edge(int s, int e, int w)

    {

        edge[++tot] = Edge(s, e, w);

        edge[++tot] = Edge(e, s, 0);

        arc[s][++amount[s]] = tot-1;

        arc[e][++amount[e]] = tot;

        return ;

    }

    bool Bfs()

    {

        bool wh[maxn];

        memset(wh, 0, sizeof wh);

        int q[maxn], st_pos = -1, en_pos = -1;

        q[++en_pos] = en;

        wh[en] = true;

        while(st_pos != en_pos)

        {

            int cur = q[++st_pos];

            for(int i = 0; i != amount[cur]+1; ++i)

            {

                Edge& ne = edge[arc[cur][i]];

                if(wh[ne.en] == false)

                {

                    dis[ne.en] = dis[cur]+1;

                    q[++en_pos] = ne.en;

                    wh[ne.en] = true;

                }

            }

        }

        if(wh[st] == false) return false;

        return true;

    }

    int Augment(int x)

    {

        int minn = INF;

        while(x != st)

        {

            Edge& e = edge[pre[x]];

            minn = min(minn, e.weight);

            x = e.st;

        }

        x = en;

        while(x != st)

        {

            int curr = pre[x];

            edge[curr].weight -= minn;

            edge[curr^1].weight += minn;

            x = edge[curr].st;

        }

        return minn;

    }

    void Advance(int x)

    {

        while(dis[st] < n)

        {

            bool wh = false;

            for(int& i = cur[x]; i != amount[x]+1; ++i)

            {

                Edge& e = edge[arc[x][i]];

                if(e.weight > 0 && dis[x] == dis[e.en]+1)

                {

                    wh = true;

                    pre[e.en] = arc[x][i];

                    x = e.en;

                    break;

                }

            }

            if(wh == false)

            {

                int m = n-1;

                for(int i = 0; i != amount[x]+1; ++i)

                {

                    Edge& e = edge[arc[x][i]];

                    if(e.weight > 0)

                    {

                        m = min(m, dis[e.en]);

                    }

                }

                if(--num[dis[x]] == 0)  return ;

                ++num[dis[x] = m+1];

                cur[x] = 0;

                if(x != st) x = edge[pre[x]].st;

            }

            if(x == en)

            {

                max_flow += Augment(en);

                x = st;

            }

        }

        return ;

    }

    int Max_flow()

    {

        Bfs();

        for(int i = 1; i != n+1; ++i)

        {

            ++num[dis[i]];

        }

        Advance(st);

        return max_flow;

    }

}doit;

int main()

{

    int a, b, c, n, m, st, en;

    freopen("test.in", "r", stdin);

    Get_All();

    read(n), read(m);

    read(st), read(en);

    doit.Init(st, en, n, m);

    for(int i = 0; i != m; ++i)

    {

        read(a), read(b), read(c);

        doit.Add_edge(a, b, c);

    }

    printf("%d\n", doit.Max_flow());

    return 0;

}

void Get_All()

{

    fseek(stdin, 0, SEEK_END);

    int file_lenth = ftell(stdin);

    rewind(stdin);

    Buffer = (char*)malloc(file_lenth*sizeof(char));

    fread(Buffer, 1, file_lenth, stdin);

    X = Buffer;

    c = *X;

    return ;

}

void Get_Int()

{

    in = 0;

    while(!isdigit(c))  c = *++X;

    while(isdigit(c))

    {

        in = in*10+c-'0';

        c = *++X;

    }

    return ;

}

3 struct+STL+BFS版

/*

About: Max_flow ISAP struct STL+BFS

Auther: kongse_qi

Date: 2017/04/30

*/

#pragma GCC optimize(3)

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <ctype.h>

#include <queue>

#define maxn 10005

#define maxm 200005

#define INF 0x3f3f3f

#define read(x) Get_Int(), x = in

#define p_b(x) push_back(x)

using namespace std;

void Get_Int();

void Get_All();

char *X, *Buffer, c;

int in;

typedef vector<int>::iterator iterator_t;

struct Edge{

      int st, en, weight;

      Edge(){}

    Edge(int s, int e, int w):

        st(s), en(e), weight(w){}

};

struct Isap{

    int st, en, tot, n, m;

    int max_flow;

    int num[maxn];

    int dis[maxn];

    int cur[maxn];

    int pre[maxn];

    vector<int> arc[maxn];

    Edge edge[maxm];

    void Init(int st, int en, int n, int m)

    {

        tot = -1;

        this -> st = st; this -> en = en;

        this -> n = n; this -> m = m;

        for(int i = 1; i != n+1; ++i)

        {

            arc[i].clear();

        }

        max_flow = 0;

        memset(cur, 0, sizeof cur);

        memset(num, 0, sizeof num);

        return ;

    }

    void Add_edge(int s, int e, int w)

    {

        edge[++tot] = Edge(s, e, w);

        edge[++tot] = Edge(e, s, 0);

        arc[s].p_b(tot-1);

        arc[e].p_b(tot);

        return ;

    }

    bool Bfs()

    {

        bool wh[maxn];

        memset(wh, 0, sizeof wh);

        queue<int> q;

        q.push(en);

        wh[en] = true;

        while(!q.empty())

        {

            int cur = q.front(); q.pop();

            for(iterator_t i = arc[cur].begin(); i != arc[cur].end(); ++i)

            {

                Edge& ne = edge[*i];

                if(wh[ne.en] == false)

                {

                    dis[ne.en] = dis[cur]+1;

                    q.push(ne.en);

                    wh[ne.en] = true;

                }

            }

        }

        if(wh[st] == false)    return false;

        return true;

    }

    int Augment(int x)

    {

        int minn = INF;

        while(x != st)

        {

            Edge& e = edge[pre[x]];

            minn = min(minn, e.weight);

            x = e.st;

        }

        x = en;

        while(x != st)

        {

            int curr = pre[x];

            edge[curr].weight -= minn;

            edge[curr^1].weight += minn;

            x = edge[curr].st;

        }

        return minn;

    }

    void Advance(int x)

    {

        while(dis[st] < n)

        {

            bool wh = false;

            for(int& i = cur[x]; i != arc[x].size(); ++i)

            {

                Edge& e = edge[arc[x][i]];

                if(e.weight > 0 && dis[x] == dis[e.en]+1)

                {

                    wh = true;

                    pre[e.en] = arc[x][i];

                    x = e.en;

                    break;

                }

            }

            if(wh == false)

            {

                int m = n-1;

                for(iterator_t i = arc[x].begin(); i != arc[x].end(); ++i)

                {

                    Edge& e = edge[*i];

                    if(e.weight > 0)

                    {

                        m = min(m, dis[e.en]);

                    }

                }

                if(--num[dis[x]] == 0)    return ;

                ++num[dis[x] = m+1];

                cur[x] = 0;

                if(x != st)    x = edge[pre[x]].st;

            }

            if(x == en)

            {

                max_flow += Augment(en);

                x = st;

            }

        }

        return ;

    }

    int Max_flow()

    {

        Bfs();

        for(int i = 1; i != n+1; ++i)

        {

            ++num[dis[i]];

        }

        Advance(st);

        return max_flow;

    }

}doit;

int main()

{

    int a, b, c, n, m, st, en;

    //freopen("test.in", "r", stdin);

    Get_All();

    read(n), read(m);

    read(st), read(en);

    doit.Init(st, en, n, m);

    for(int i = 0; i != m; ++i)

    {

        read(a), read(b), read(c);

        doit.Add_edge(a, b, c);

    }

    printf("%d\n", doit.Max_flow());

    return 0;

}

void Get_All()

{

    fseek(stdin, 0, SEEK_END);

    int file_lenth = ftell(stdin);

    rewind(stdin);

    Buffer = (char*)malloc(file_lenth*sizeof(char));

    fread(Buffer, 1, file_lenth, stdin);

    X = Buffer;

    c = *X;

    return ;

}

void Get_Int()

{

    in = 0;

    while(!isdigit(c))    c = *++X;

    while(isdigit(c))

    {

        in = in*10+c-'0';

        c = *++X;

    }

    return ;

}

结构体版实际上就是将函数作为结构体的成员函数运行，在主函数中调用时逻辑会更加清晰（分区很明显）。

---

实测结果：

O2优化情况下：
1.耗时：115ms
内存：17281kb

2.耗时：80ms
内存：23304kb

3.耗时：103ms
内存：17281kb

其实差距不大。

不开O2的情况下：

1.耗时：322ms
内存：17429kb

2.耗时：141ms
内存：23304kb

3.耗时：323ms
内存：17292kb
（结果不一定十分稳定）
因此不开优化的STL是非常不建议使用的。
STL的快速与便捷只有在开启优化的情况下才能兼得。

---

附压行代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <ctype.h>

#include <vector>

#define maxn 10005

#define maxm 200005

#define INF 0x3f3f3f

using namespace std;

struct Edge{

    int st, en, weight;

    Edge(){}

    Edge(int s, int e, int w):

        st(s), en(e), weight(w){}

};

struct Isap{

    int st, en, tot, n, m, max_flow;

    int num[maxn], dis[maxn], cur[maxn], pre[maxn], arc[maxn][100], amount[maxn];

    vector<Edge> edge;

    void Init(int st, int en, int n, int m){

        tot = -1;

        this -> st = st; this -> en = en;

        this -> n = n; this -> m = m;

        max_flow = 0;

        edge.resize(m*2);

        memset(cur, 0, sizeof cur);

        memset(num, 0, sizeof num);

        memset(amount, -1, sizeof amount);

    }

    void Add_edge(int s, int e, int w){

        edge[++tot] = Edge(s, e, w);

        edge[++tot] = Edge(e, s, 0);

        arc[s][++amount[s]] = tot-1;

        arc[e][++amount[e]] = tot;

    }

    void Bfs(){

        bool wh[maxn] = {0};

        int q[maxn], st_pos = -1, en_pos = -1;

        q[++en_pos] = en;

        wh[en] = true;

        while(st_pos != en_pos){

            int cur = q[++st_pos];

            for(int i = 0; i != amount[cur]+1; ++i){

                Edge ne = edge[arc[cur][i]];

                if(wh[ne.en] == false){

                    dis[ne.en] = dis[cur]+1;

                    q[++en_pos] = ne.en;

                    wh[ne.en] = true;

                }

            }

        }

    }

    int Augment(){

        int minn = INF, curr;

        Edge e;

        for(int x = en; x != st; ){

            e = edge[pre[x]];

            minn = min(minn, e.weight);

            x = e.st;

        }

        for(int x = en; x != st;){

            curr = pre[x];

            edge[curr].weight -= minn;

            edge[curr^1].weight += minn;

            x = edge[curr].st;

        }

        return minn;

    }

    void Advance(int x){

        while(dis[st] < n){

            bool wh = false;

            for(int& i = cur[x]; i != amount[x]+1; ++i){

                Edge &e = edge[arc[x][i]];

                if(e.weight > 0 && dis[x] == dis[e.en]+1){

                    wh = true;

                    pre[e.en] = arc[x][i];

                    x = e.en;

                    break;

                }

            }

            if(wh == false){

                int minn = n-1;

                for(int i = 0; i != amount[x]+1; ++i){

                    Edge& e = edge[arc[x][i]];

                    if(e.weight > 0)

                        minn = min(minn, dis[e.en]);

                }

                if(--num[dis[x]] == 0)  return ;

                ++num[dis[x] = minn+1];

                cur[x] = 0;

                if(x != st) x = edge[pre[x]].st;

            }

            if(x == en) {

                max_flow += Augment();

                x = st;

            }

        }

    }

    int Max_flow(){

        Bfs();

        for(int i = 1; i != n+1; ++i)

            ++num[dis[i]];

        Advance(st);

        return max_flow;

    }

}doit;

int main(){

    int a, b, c, n, m, st, en;

    //freopen("test.in", "r", stdin);

    scanf("%d%d", &n, &m);

    st = 1, en = n;

    doit.Init(st, en, n, m);

    for(int i = 0; i != m; ++i){

        scanf("%d%d%d", &a, &b, &c);

        doit.Add_edge(a, b, c);

    }

    printf("%d\n", doit.Max_flow());

    return 0;

}

（121行total）

---

自此结束。
箜瑟_qi 2017.04.30 23:20
四月最后一篇。