最大流 Dinic + Sap 模板

漂亮蓝影

　　不说别的，直接上模板。
　　
　　Dinic+当前弧优化：



struct Edge{
int x,y,c,ne;
}e[M*2];
int be[N],all;
int d[N],q[N];
int stack[N],top;//栈存的是边
int cur[N];//当前弧优化

void add(int x, int y, int z)//需保证相反边第一个为偶数
{
e[all].x=x; e[all].y=y; e[all].c=z;
e[all].ne=be[x];
be[x]=all++;
e[all].x=y; e[all].y=x; e[all].c=0;
e[all].ne=be[y];
be[y]=all++;
}

bool BFS(int s, int t)//化为层次图 使得边数从m降低为n 复杂度随之下降
{
memset(d,-1,sizeof(d));
int head=0,tail=0;
q[++tail]=s;
d=0;
while(head!=tail)
{
int u=q[++head];
for(int i=be; i!=-1; i=e.ne)
if(e.c>0 && d[e.y]==-1){
d[e.y]=d+1;
q[++tail]=e.y;
if(tail==N-1) tail=0;
if(e.y==t) return 1;
}
}
return 0;
}
int Dinic(int s, int t)//防止爆栈 用stack模拟递归
{
int ans=0;
while(BFS(s,t))
{
memcpy(cur,be,sizeof(be));
int u=s;
top=0;//dfs开始 清空栈
while(1)
{
if(u==t)
{
int minc=1000000000,mini;
for(int i=0; i<top; i++)
if(minc>e[stack].c)
{
minc=e[stack].c;
mini=i;//以便之后回到这继续增广
                    }
for(int i=0; i<top; i++)
{
e[stack].c-=minc;
e[stack^1].c+=minc;//第一个二进制取反 即取相反边
                }
ans+=minc;
top=mini;
u=e[stack[mini]].x;
}
for(int i=cur; i!=-1; cur=i=e[cur].ne)
if(e.c>0 && d[e.y]==d[e.x]+1) break;
if(cur!=-1)
{
stack[top++]=cur;
u=e[cur].y;
}else
{
if(top==0) break;   //循环结束标志
d=-1;//当前节点不在增广路中 删除
u=e[stack[--top]].x;//回溯
            }
}
}
return ans;
}
　　ISAP+GAP+当前弧优化：



struct Edge{
int x,y,c,ne;
}e[M*2];
int x,y,z,n,m,s,t;
int be[N],all;
int d[N],q[N];
int stack[N];//模拟递归
int gap[N],cur[N];//gap优化+当前弧优化
void add(int x, int y, int z)//保证第一个为偶数
{
e[all].x=x; e[all].y=y; e[all].c=z;
e[all].ne=be[x];
be[x]=all++;
e[all].x=y; e[all].y=x; e[all].c=0;
e[all].ne=be[y];
be[y]=all++;
}
void BFS(int s, int t)
{
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
gap[0]=1;
int head=0,tail=0;
q[++tail]=t;
d[t]=0;
while(head!=tail)
{
int u=q[++head];
for(int i=be; i!=-1; i=e.ne)
if(d[e.y]==-1)
{
d[e.y]=d+1;
q[++tail]=e.y;
gap[d[e.y]]++;
}
}
}
int sap(int s, int t, int n)
{
int ans=0;
BFS(s,t);
memcpy(cur,be,sizeof(be));
int top=0;
int u=s;
while(d<n)
{
if(u==t)
{
int minc=1000000000,mini;
for(int i=0; i<top; i++)
if(minc>e[stack].c)
{
minc=e[stack].c;
mini=i;
}
for(int i=0; i<top; i++)
{
e[stack].c-=minc;
e[stack^1].c+=minc;
}
ans+=minc;
top=mini;
u=e[stack[mini]].x;
continue;
}
for(int i=cur; i!=-1; cur=i=e.ne)//当前弧优化
if(e.c>0 && d[e.y]+1==d) break;
if(cur!=-1)
{
stack[top++]=cur;
u=e[cur].y;
}else
{
int mind=n;
for(int i=be; i!=-1; i=e.ne)//更新距离标号
if(e.c>0 && mind>d[e.y])
{
mind=d[e.y];
cur=i;
}
gap[d]--;
if(!gap[d]) return ans;//gap表示当前距离的点有多少个 一旦==0 说明断层直接退出循环
d=mind+1;
gap[d]++;
if(u!=s) u=e[stack[--top]].x;
}
}
return ans;
}
void init()
{
all=0;
memset(be,-1,sizeof(be));
}