用了一年的SAP模板T了，学习了一下非递归的写法
SAP算法的核心：
维护距离标号的方法是这样的：当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。由于距离标号的存在，由于“怎么走都是最短路”，所以就可以采用DFS找增广路，用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时，栈中指向它的那条弧肯定已经不是允许弧了，所以就让它出栈，并继续用栈顶的弧的端点增广。为了使每次找增广路的时间变成均摊O(V)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条允许弧，就把这条弧设为当前弧；改变距离标号时，把当前弧重新设为邻接表的第一条弧，还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。
还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的边退栈，这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化，由于当前边结构的存在，我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。
优化：
1.邻接表优化：
如果顶点多的话，往往N^2存不下，这时候就要存边：
存每条边的出发点，终止点和价值，然后排序一下，再记录每个出发点的位置。以后要调用从出发点出发的边时候，只需要从记录的位置开始找即可（其实可以用链表）。优点是时间加快空间节省，缺点是编程复杂度将变大，所以在题目允许的情况下，建议使用邻接矩阵。
2.GAP优化：
如果一次重标号时，出现距离断层，则可以证明ST无可行流，此时则可以直接退出算法。
3.当前弧优化：
为了使每次找增广路的时间变成均摊O(V)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条允许弧，就把这条弧设为当前弧；改变距离标号时，把当前弧重新设为邻接表的第一条弧。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1<<30
#define N 20010
#define M 240100
using namespace std;
struct Edge{
int v,cap,next;
}edge[M*2];
int n,k,dis[N],gap[N],head[N],pre[N],cur[N]; //n为总点数
void addedge(int u,int v,int c1,int c2){
edge[k].v=v;
edge[k].cap=c1;
edge[k].next=head[u];
head[u]=k++;
edge[k].v=u;
edge[k].cap=c2;
edge[k].next=head[v];
head[v]=k++;
}
void init(){
memset(head,-1,sizeof(head));
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
k=0;
}
int sap(int s,int t){
for(int i=0;i<n;i++)cur[i]=head[i];//用cur数组去表示当前的一条路径cur[u]为从u指出的边的编号
int u=pre[s]=s,maxflow=0,aug=-1;
gap[0]=n; // gap表示初始时dis为0的点有n个
while(dis[s]<n){
loop: for(int &i=cur[u];i!=-1;i=edge[i].next){ //注意i要引用cur[u]的地址
int v=edge[i].v;
if(edge[i].cap && dis[u]==dis[v]+1){
if(aug==-1 || aug>edge[i].cap)
aug=edge[i].cap;
pre[v]=u;
u=v;
if(v==t){
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u]){
edge[cur[u]].cap-=aug;
edge[cur[u]^1].cap+=aug;
}
aug=-1;
}
goto loop;
}
}
int mindis=n;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(edge[i].cap && mindis>dis[v]){
cur[u]=i;
mindis=dis[v];
}
}
if((--gap[dis[u]])==0)break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
int main(){
int v,e,i,j,a,b,c;
scanf("%d %d",&v,&e);
n=v+2;
init();
for(i=1;i<=v;i++){
scanf("%d %d",&a,&b);
addedge(0,i,a,0);
addedge(i,v+1,b,0);
}
for(i=1;i<=e;i++){
scanf("%d %d %d",&a,&b,&c);
addedge(a,b,c,c);
}
printf("%d\n",sap(0,v+1));
return 0;
}