最大流模板（SAP算法）（邻接表形式）

dfee

　　最大流的SAP模板，用了很多次了。今天总结贴下(虽然代码不够精简，但是自己写的也总算看起来明白些，不容易错）
　　据说没有可以卡SAP的最大流。。。
　　
　　



const int MAXN=20010;//点数的最大值
const int MAXM=880010;//边数的最大值
const int INF=0x3f3f3f3f;
struct Node
{
int from,to,next;
int cap;
}edge[MAXM];
int tol;
int head[MAXN];
int dep[MAXN];
int gap[MAXN];//gap[x]=y :说明残留网络中dep==x的个数为y
int n;//n是总的点的个数，包括源点和汇点
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w)
{
edge[tol].from=u;
edge[tol].to=v;
edge[tol].cap=w;
edge[tol].next=head;
head=tol++;
edge[tol].from=v;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].next=head[v];
head[v]=tol++;
}
void BFS(int start,int end)
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=1;
int que[MAXN];
int front,rear;
front=rear=0;
dep[end]=0;
que[rear++]=end;
while(front!=rear)
{
int u=que[front++];
if(front==MAXN)front=0;
for(int i=head;i!=-1;i=edge.next)
{
int v=edge.to;
if(dep[v]!=-1)continue;
que[rear++]=v;
if(rear==MAXN)rear=0;
dep[v]=dep+1;
++gap[dep[v]];
}
}
}
int SAP(int start,int end)
{
int res=0;
BFS(start,end);
int cur[MAXN];
int S[MAXN];
int top=0;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep[start]<n)
{
if(u==end)
{
int temp=INF;
int inser;
for(i=0;i<top;i++)
if(temp>edge[S].cap)
{
temp=edge[S].cap;
inser=i;
}
for(i=0;i<top;i++)
{
edge[S].cap-=temp;
edge[S^1].cap+=temp;
}
res+=temp;
top=inser;
u=edge[S[top]].from;
}
if(u!=end&&gap[dep-1]==0)//出现断层，无增广路
break;
for(i=cur;i!=-1;i=edge.next)
if(edge.cap!=0&&dep==dep[edge.to]+1)
break;
if(i!=-1)
{
cur=i;
S[top++]=i;
u=edge.to;
}
else
{
int min=n;
for(i=head;i!=-1;i=edge.next)
{
if(edge.cap==0)continue;
if(min>dep[edge.to])
{
min=dep[edge.to];
cur=i;
}
}
--gap[dep];
dep=min+1;
++gap[dep];
if(u!=start)u=edge[S[--top]].from;
}
}
return res;
}