网络流sap算法模版

dsfdsf

　　递归版sap：



#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 310
#define M 50010
#define inf 1<<30
using namespace std;
struct Edge{
int to,val,next;
}edge[M];
int index[N],d[N],gap[N],e;
void addedge(int from,int to,int val)
{
edge[e].to=to;
edge[e].val=val;
edge[e].next=index[from];
index[from]=e++;
edge[e].to=from;
edge[e].val=0;
edge[e].next=index[to];
index[to]=e++;
}
int source,des,n,m;
int dfs(int pos,int flow)
{
if(pos==des)
return flow;
int i,j,v,val,lv,mind,c;
mind=n-1;//初始最小标号为n-1
lv=flow;
for(i=index[pos];i!=-1;i=edge.next)
{
v=edge.to;
val=edge.val;
if(val)
{
if(d[v]+1==d[pos])
{
c=min(lv,val);//对于该点的最小可行流
c=dfs(v,c);
edge.val-=c;//更新剩余图
edge[i^1].val+=c;
lv-=c;
if(d[source]>=n)return flow-lv;
if(lv==0) break;
}
if(d[v]<mind)mind=d[v];//找出与pos相连的点的最小标号
        }
}
if(lv==flow)//没有找到增广路劲，进行标号更新
    {
--gap[d[pos]];
if(!gap[d[pos]])
d[source]=n;
d[pos]=mind+1;
++gap[d[pos]];
}
return flow-lv;
}
int sap(int st,int de)
{
source=st;
des=de;
memset(d,0,sizeof(d));
memset(gap,0,sizeof(gap));
gap[0]=n;//初始标号为0的有n个.
int ans=0;
while(d[st]<n)//n是图中点的个数     {
ans+=dfs(st,inf);
//cout<<d[st]<<endl;
    }
return ans;
}
void init()
{
e=0;
memset(index,-1,sizeof(index));
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
init();
int i;
int ll,rr,cap;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&ll,&rr,&cap);
addedge(ll,rr,cap);
}
printf("%d\n",sap(1,n));     }
return 0;
}
　　非递归版sap:



#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 6010
#define Maxm 200000
#define LL __int64
#define Abs(a) (a)>0?(a):(-a)
using namespace std;
struct Edge{
int from,to,next;
LL val;
}edge[Maxm];
int index[Maxn],d[Maxn],gap[Maxn],e,vi[Maxn],n,m;
LL value[Maxn];
LL inf=0;
inline void addedge(int from,int to,LL val)//有向边
{
edge[e].from=from;
edge[e].to=to;
edge[e].val=val;
edge[e].next=index[from];
index[from]=e++;
edge[e].from=to;
edge[e].to=from;
edge[e].val=0;
edge[e].next=index[to];
index[to]=e++;
}
int prev[Maxn],curr[Maxn];
LL sap(int src,int des,int N)//分别为起点源点和点的数目
{
bool flag;
int u=src;
LL cnt=inf,sum=0;
memset(d,0,sizeof(d));
memset(gap,0,sizeof(gap)); gap[0]=N;
while(d[src]!=N)
{
flag=false;
for(int i=index;i!=-1;i=edge.next)
{
if(edge.val&&d[edge.to]==d-1)
{
cnt=min(cnt,edge.val);
prev[edge.to]=u;
curr[edge.to]=i;
u=edge.to;
flag=true;
if(u==des)
{
while(u!=src)
{
edge[curr].val-=cnt;
edge[curr^1].val+=cnt;
u=prev;
}
sum+=cnt;
cnt=inf;
}
else break;
}
}
if(!flag)
{
if(!--gap[d]) break;
else
{
d=N;
for(int i=index;i!=-1;i=edge.next)
{
if(edge.val) d=min(d,d[edge.to]+1);
}
gap[d]++;
if(u!=src) u=prev;
}
}
}
return sum;
}
void init()
{
e=0;
inf=0;
memset(index,-1,sizeof(index));
memset(vi,0,sizeof(vi));
}