最大流 Dinic + Sap 模板
不说别的，直接上模板。Dinic+当前弧优化：
struct Edge{
int x,y,c,ne;
}e;
int be,all;
int d,q;
int stack,top;//栈存的是边
int cur;//当前弧优化
void add(int x, int y, int z)//需保证相反边第一个为偶数
{
e.x=x; e.y=y; e.c=z;
e.ne=be;
be=all++;
e.x=y; e.y=x; e.c=0;
e.ne=be;
be=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.y]==-1){
d.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].c)
{
minc=e].c;
mini=i;//以便之后回到这继续增广
}
for(int i=0; i<top; i++)
{
e].c-=minc;
e^1].c+=minc;//第一个二进制取反 即取相反边
}
ans+=minc;
top=mini;
u=e].x;
}
for(int i=cur; i!=-1; cur=i=e].ne)
if(e.c>0 && d.y]==d.x]+1) break;
if(cur!=-1)
{
stack=cur;
u=e].y;
}else
{
if(top==0) break; //循环结束标志
d=-1;//当前节点不在增广路中 删除
u=e].x;//回溯
}
}
}
return ans;
}
ISAP+GAP+当前弧优化：
struct Edge{
int x,y,c,ne;
}e;
int x,y,z,n,m,s,t;
int be,all;
int d,q;
int stack;//模拟递归
int gap,cur;//gap优化+当前弧优化
void add(int x, int y, int z)//保证第一个为偶数
{
e.x=x; e.y=y; e.c=z;
e.ne=be;
be=all++;
e.x=y; e.y=x; e.c=0;
e.ne=be;
be=all++;
}
void BFS(int s, int t)
{
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
gap=1;
int head=0,tail=0;
q[++tail]=t;
d=0;
while(head!=tail)
{
int u=q[++head];
for(int i=be; i!=-1; i=e.ne)
if(d.y]==-1)
{
d.y]=d+1;
q[++tail]=e.y;
gap.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].c)
{
minc=e].c;
mini=i;
}
for(int i=0; i<top; i++)
{
e].c-=minc;
e^1].c+=minc;
}
ans+=minc;
top=mini;
u=e].x;
continue;
}
for(int i=cur; i!=-1; cur=i=e.ne)//当前弧优化
if(e.c>0 && d.y]+1==d) break;
if(cur!=-1)
{
stack=cur;
u=e].y;
}else
{
int mind=n;
for(int i=be; i!=-1; i=e.ne)//更新距离标号
if(e.c>0 && mind>d.y])
{
mind=d.y];
cur=i;
}
gap]--;
if(!gap]) return ans;//gap表示当前距离的点有多少个 一旦==0 说明断层直接退出循环
d=mind+1;
gap]++;
if(u!=s) u=e].x;
}
}
return ans;
}
void init()
{
all=0;
memset(be,-1,sizeof(be));
}
页:
[1]