网络流sap算法模版
递归版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;
int index,d,gap,e;
void addedge(int from,int to,int val)
{
edge.to=to;
edge.val=val;
edge.next=index;
index=e++;
edge.to=from;
edge.val=0;
edge.next=index;
index=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;i!=-1;i=edge.next)
{
v=edge.to;
val=edge.val;
if(val)
{
if(d+1==d)
{
c=min(lv,val);//对于该点的最小可行流
c=dfs(v,c);
edge.val-=c;//更新剩余图
edge.val+=c;
lv-=c;
if(d>=n)return flow-lv;
if(lv==0) break;
}
if(d<mind)mind=d;//找出与pos相连的点的最小标号
}
}
if(lv==flow)//没有找到增广路劲，进行标号更新
{
--gap];
if(!gap])
d=n;
d=mind+1;
++gap];
}
return flow-lv;
}
int sap(int st,int de)
{
source=st;
des=de;
memset(d,0,sizeof(d));
memset(gap,0,sizeof(gap));
gap=n;//初始标号为0的有n个.
int ans=0;
while(d<n)//n是图中点的个数 {
ans+=dfs(st,inf);
//cout<<d<<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;
int index,d,gap,e,vi,n,m;
LL value;
LL inf=0;
inline void addedge(int from,int to,LL val)//有向边
{
edge.from=from;
edge.to=to;
edge.val=val;
edge.next=index;
index=e++;
edge.from=to;
edge.to=from;
edge.val=0;
edge.next=index;
index=e++;
}
int prev,curr;
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=N;
while(d!=N)
{
flag=false;
for(int i=index;i!=-1;i=edge.next)
{
if(edge.val&&d.to]==d-1)
{
cnt=min(cnt,edge.val);
prev.to]=u;
curr.to]=i;
u=edge.to;
flag=true;
if(u==des)
{
while(u!=src)
{
edge].val-=cnt;
edge^1].val+=cnt;
u=prev;
}
sum+=cnt;
cnt=inf;
}
else break;
}
}
if(!flag)
{
if(!--gap]) break;
else
{
d=N;
for(int i=index;i!=-1;i=edge.next)
{
if(edge.val) d=min(d,d.to]+1);
}
gap]++;
if(u!=src) u=prev;
}
}
}
return sum;
}
void init()
{
e=0;
inf=0;
memset(index,-1,sizeof(index));
memset(vi,0,sizeof(vi));
}
页:
[1]