ISAP算法
ISAP（Improved Shortest Augumenting Path）算法是改进版的SAP算法，如果对效率要求很高的时候，可以用该算法。
（1）概述：算法基于这样的一个事实：每次增广之后，任意结点到汇点（在残余网络中）的最短距离都不会减小。这样，我们可以利用d[i[表示结点i到汇点的距离的下界。然后再增广过程当中不断地修改这个下界。增广的时候和Dinic算法类似，只允许沿着d[i]==d[j]+1的弧(i,j)走。
不难证明，d[i[满足两个条件：(1)d[t]=0;(2)对任意的弧(i,j) d[i]≤d[j]+1。因为最坏的情况就是s到t是一条链，此时等号成立。因此，当d[s]≥n时，残余网络中不存在s-t路。
那么与Dinic算法类似，事先逆向bfs，找增广的过程就是沿着“允许弧”（即满足f<c且d[i]==d[j]+1的弧）往前走。（称为“前进”）。如果向前走不动了，那么就要考虑原路返回（称为“撤退”）。此时把d[i]修改为min{d[j]}+1即可。因为要满足d函数的条件(2)。修改后，原来的i值的个数就减少一个，而新i值的个数多一个。在程序中，用num数组来保存所有距离的个数，当把距离值从x修改为y时，num[x]–,num[y]++即可，然后检查num[x]是否为0，如果是0，那么s-t不连通，算法终止。原因显而易见：比如s-t的距离是3，，如果距离为2的情况都已经没了，更别提走到距离为1的点了。这就是所谓的“gap优化”。
通过之前的分析，在数据结构方面，该算法只比Dinic算法的数据结构多了两个数组：用于记录父边以便于撤退的数组p，以及标记距离个数的数组num。增广的时候分为两步，第一步逆推求出可改进量a（即残余量的最小值）；第二步再逆推一遍，进行增广。主过程中，x走到汇点时增广。
#include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1000#define INF 100000000struct Edge{int from,to,cap,flow;};struct ISAP{int n,m,s,t;vector<Edge>edges;vector<int>G[N];bool vis[N];int d[N],cur[N];int p[N],num[N];//比Dinic算法多了这两个数组，p数组标记父亲结点，num数组标记距离d[i]存在几个void addedge(int from,int to,int cap){edges.push_back((Edge){from,to,cap,0});edges.push_back((Edge){to,from,0,0});int m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);}int Augumemt(){int x=t,a=INF;while(x!=s)//找最小的残量值{Edge&e=edges[p[x]];a=min(a,e.cap-e.flow);x=edges[p[x]].from;}x=t;while(x!=s)//增广{edges[p[x]].flow+=a;edges[p[x]^1].flow-=a;x=edges[p[x]].from;}return a;}void bfs()//逆向进行bfs{memset(vis,0,sizeof(vis));queue<int>q;q.push(t);d[t]=0;vis[t]=1;while(!q.empty()){int x=q.front();q.pop();int len=G[x].size();for(int i=0;i<len;i++){Edge&e=edges[G[x][i]];if(!vis[e.from]&&e.cap>e.flow){vis[e.from]=1;d[e.from]=d[x]+1;q.push(e.from);}}}}int Maxflow(int s,int t)//根据情况前进或者后退，走到汇点时增广{this->s=s;this->t=t;int flow=0;bfs();memset(num,0,sizeof(num));for(int i=0;i<n;i++)num[d[i]]++;int x=s;memset(cur,0,sizeof(cur));while(d[s]<n){if(x==t)//走到了汇点，进行增广{flow+=Augumemt();x=s;//增广后回到源点}int ok=0;for(int i=cur[x];i<G[x].size();i++){Edge&e=edges[G[x][i]];if(e.cap>e.flow&&d[x]==d[e.to]+1){ok=1;p[e.to]=G[x][i];//记录来的时候走的边，即父边cur[x]=i;x=e.to;//前进break;}}if(!ok)//走不动了，撤退{int m=n-1;//如果没有弧，那么m+1就是n，即d[i]=nfor(int i=0;i<G[x].size();i++){Edge&e=edges[G[x][i]];if(e.cap>e.flow)m=min(m,d[e.to]);}if(–num[d[x]]==0)break;//如果走不动了，且这个距离值原来只有一个，那么s-t不连通，这就是所谓的“gap优化”num[d[x]=m+1]++;cur[x]=0;if(x!=s)x=edges[p[x]].from;//退一步，沿着父边返回}}return flow;}};int main(){// freopen("t.txt","r",stdin);ISAP sap;while(cin>>sap.n>>sap.m){for(int i=0;i<sap.m;i++){int from,to,cap;cin>>from>>to>>cap;sap.addedge(from,to,cap);}cin>>sap.s>>sap.t;cout<<sap.Maxflow(sap.s,sap.t)<<endl;}return 0;}
志在山顶的人，不会贪念山腰的风景。
