一般预流推进法模版
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include<queue>
using namespace std;
#define INF 99999999
const int maxn =250;
const int maxm =250;
const int oo = 0x7fffffff;
struct push_relablel//一般预流推进法求最大流，时间复杂度O(n*n*m)
{int res[maxn][maxn];//残留网络int h[maxn];//高度int ef[maxn];//余流int n;//点数int max_flow;//最大流queue<int>que;//活动定点队列int u,v,p,i;int vis[maxn];void init(int x){n=x;memset(h,0,sizeof(h));memset(ef,0,sizeof(ef));memset(res,0,sizeof(res));}void add(int u,int v,int w){res[u][v]+=w;}int ans(int s,int t){max_flow=0;h[s]=n;ef[s]=oo;ef[t]=-oo;while(!que.empty())que.pop();que.push(s);while(!que.empty()){u=que.front();que.pop();for(i=1;i<=n;i++){v=i;if(res[u][v]<ef[u])p=res[u][v];else p=ef[u];if(p>0&&(u==s||h[u]==h[v]+1)){res[u][v]-=p;res[v][u]+=p;if(v==t)max_flow+=p;ef[u]-=p;ef[v]+=p;if(v!=s&&v!=t)que.push(v);}}if(u!=s&&u!=t&&ef[u]>0){h[u]++;que.push(u);}}return max_flow;}
}G;
int main()
{int m,n,u,v,w;while(~scanf("%d%d",&m,&n)){G.init(n);while(m--){scanf("%d%d%d",&u,&v,&w);G.add(u,v,w);}cout<<G.ans(1,n)<<endl;}return 0;
}
最高标号预流推进算法模版：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include<queue>
using namespace std;
#define INF 99999999
const int maxn =250;
const int maxm =250;
const int oo = 0x7fffffff;
struct list
{int x;int h;bool friend operator <(const list &a,const list &b){return a.h<b.h;}
}q;
struct push_relablel//最高标号预流推进算法，时间复杂度O(n*n*sqrt（m）)
{int res[maxn][maxn];//残留网络int h[maxn];//高度int ef[maxn];//余流int n;//点数int max_flow;//最大流// queue<int>que;//活动定点队列priority_queue<list>que;int u,v,p,i;int vis[maxn];void init(int x){n=x;memset(h,0,sizeof(h));memset(ef,0,sizeof(ef));memset(res,0,sizeof(res));}void add(int u,int v,int w){res[u][v]+=w;}int ans(int s,int t){max_flow=0;h[s]=n;ef[s]=oo;ef[t]=-oo;while(!que.empty())que.pop();q.x=s;q.h=h[s];que.push(q);while(!que.empty()){q=que.top();que.pop();u=q.x;for(i=1;i<=n;i++){v=i;if(res[u][v]<ef[u])p=res[u][v];else p=ef[u];if(p>0&&(u==s||h[u]==h[v]+1)){res[u][v]-=p;res[v][u]+=p;if(v==t)max_flow+=p;ef[u]-=p;ef[v]+=p;if(v!=s&&v!=t){q.x=v;q.h=h[v];que.push(q);}}}if(u!=s&&u!=t&&ef[u]>0){h[u]++;q.x=u;q.h=h[u];que.push(q);}}return max_flow;}
}G;
int main()
{int m,n,u,v,w;while(~scanf("%d%d",&m,&n)){G.init(n);while(m--){scanf("%d%d%d",&u,&v,&w);G.add(u,v,w);}cout<<G.ans(1,n)<<endl;}return 0;
}sap+gap优化
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include<queue>
using namespace std;
#define INF 99999999
const int maxn =1110;
const int maxm =220000;
const int oo = 1<<29;
struct Arclist
{int cnt, head[maxn], dis[maxn];int cur[maxn], pre[maxn], gap[maxn], aug[maxn];struct node{int u, v, w, next;}edge[maxm];void init(){cnt = 0;memset(head,-1,sizeof(head));}void add(int u, int v, int w){// cout<<u<<" "<<v<<" "<<w<<endl;edge[cnt].u = u;edge[cnt].v = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;edge[cnt].u = v;edge[cnt].v = u;edge[cnt].w = 0;edge[cnt].next = head[v];head[v] = cnt++;}int sap(int s, int e, int n){int max_flow = 0, u = s;int mindis;for(int i = 0; i <= n; i++){cur[i] = head[i];dis[i] = 0;gap[i] = 0;}aug[s] = oo;pre[s] = -1;gap[0] = n;while(dis[s]<n){bool flag = false;if(u==e){max_flow += aug[e];for(int v = pre[e]; v != -1; v = pre[v]){int id = cur[v];edge[id].w -= aug[e];edge[id^1].w += aug[e];aug[v] -= aug[e];if(edge[id].w==0) u = v;}}for(int id = cur[u]; id != -1; id = edge[id].next){int v = edge[id].v;if(edge[id].w>0 && dis[u]==dis[v]+1){flag = true;pre[v] = u;cur[u] = id;aug[v] = std::min(aug[u], edge[id].w);u = v;break;}}if(flag==false){if(--gap[dis[u]]==0) break;mindis = n;cur[u] = head[u];for(int id = head[u]; id != -1; id = edge[id].next){int v = edge[id].v;if(edge[id].w>0 && dis[v]<mindis){mindis = dis[v];cur[u] = id;}}dis[u] = mindis+1;++gap[dis[u]];if(u!=s) u = pre[u];}}return max_flow;}
}G;
int main()
{int m,n,u,v,w;while(~scanf("%d%d",&m,&n)){G.init();while(m--){scanf("%d%d%d",&u,&v,&w);G.add(u,v,w);}cout<<G.sap(1,n,n)<<endl;}return 0;
}