递归版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[i].next) { v=edge[i].to; val=edge[i].val; if(val) { if(d[v]+1==d[pos]) { c=min(lv,val);//对于该点的最小可行流 c=dfs(v,c); edge[i].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 ",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[u];i!=-1;i=edge[i].next) { if(edge[i].val&&d[edge[i].to]==d[u]-1) { cnt=min(cnt,edge[i].val); prev[edge[i].to]=u; curr[edge[i].to]=i; u=edge[i].to; flag=true; if(u==des) { while(u!=src) { edge[curr[u]].val-=cnt; edge[curr[u]^1].val+=cnt; u=prev[u]; } sum+=cnt; cnt=inf; } else break; } } if(!flag) { if(!--gap[d[u]]) break; else { d[u]=N; for(int i=index[u];i!=-1;i=edge[i].next) { if(edge[i].val) d[u]=min(d[u],d[edge[i].to]+1); } gap[d[u]]++; if(u!=src) u=prev[u]; } } } return sum; } void init() { e=0; inf=0; memset(index,-1,sizeof(index)); memset(vi,0,sizeof(vi)); }