最大流模板（SAP算法）（邻接表形式）
最大流的SAP模板，用了很多次了。今天总结贴下(虽然代码不够精简，但是自己写的也总算看起来明白些，不容易错）据说没有可以卡SAP的最大流。。。
const int MAXN=20010;//点数的最大值
const int MAXM=880010;//边数的最大值
const int INF=0x3f3f3f3f;
struct Node
{
int from,to,next;
int cap;
}edge;
int tol;
int head;
int dep;
int gap;//gap=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.from=u;
edge.to=v;
edge.cap=w;
edge.next=head;
head=tol++;
edge.from=v;
edge.to=u;
edge.cap=0;
edge.next=head;
head=tol++;
}
void BFS(int start,int end)
{
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap=1;
int que;
int front,rear;
front=rear=0;
dep=0;
que=end;
while(front!=rear)
{
int u=que;
if(front==MAXN)front=0;
for(int i=head;i!=-1;i=edge.next)
{
int v=edge.to;
if(dep!=-1)continue;
que=v;
if(rear==MAXN)rear=0;
dep=dep+1;
++gap];
}
}
}
int SAP(int start,int end)
{
int res=0;
BFS(start,end);
int cur;
int S;
int top=0;
memcpy(cur,head,sizeof(head));
int u=start;
int i;
while(dep<n)
{
if(u==end)
{
int temp=INF;
int inser;
for(i=0;i<top;i++)
if(temp>edge].cap)
{
temp=edge].cap;
inser=i;
}
for(i=0;i<top;i++)
{
edge].cap-=temp;
edge^1].cap+=temp;
}
res+=temp;
top=inser;
u=edge].from;
}
if(u!=end&&gap-1]==0)//出现断层，无增广路
break;
for(i=cur;i!=-1;i=edge.next)
if(edge.cap!=0&&dep==dep.to]+1)
break;
if(i!=-1)
{
cur=i;
S=i;
u=edge.to;
}
else
{
int min=n;
for(i=head;i!=-1;i=edge.next)
{
if(edge.cap==0)continue;
if(min>dep.to])
{
min=dep.to];
cur=i;
}
}
--gap];
dep=min+1;
++gap];
if(u!=start)u=edge].from;
}
}
return res;
}
页:
[1]