【模板】最大流 加强版 / 预流推进

给定 n 个点，m 条有向边，给定每条边的容量，求从点 s 到点 t 的最大流。 $DinicDinic$算法复杂度上界为$n^{2}mn^2m$，可以优化到$nmlogCnmlogC$ ，$CC$是最大的流量，代补。

$HLPPHLPP$算法复杂度上界为$n^2\sqrt{m}n^2\; \backslash sqrt\{m\}$，并且在经过优化后这种算法在数据随机的情况下速度也不亚于上述两种增广路算法。

常规：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e4+5,M=2e5+5,inf=0x3f3f3f3f;
int n,m,s,t,tot=1;
int to[M<<1],w[M<<1],head[N],Next[M<<1];
int h[N],e[N],gap[N<<1],inq[N];//节点高度是可以到达2n-1的
struct cmp {
	inline bool operator()(int a,int b) const {
		return h[a]<h[b];//因为在优先队列中的节点高度不会改变，所以可以直接比较
	}
};
queue<int> que;
priority_queue<int,vector<int>,cmp> pque;
inline void add(int x,int y,int z) {
	to[++tot]=y; w[tot]=z; Next[tot]=head[x]; head[x]=tot;
	to[++tot]=x; w[tot]=0;  Next[tot]=head[y]; head[y]=tot;
}
inline bool bfs() {
	int now,i;
	memset(h+1,0x3f,sizeof(int)*n);
	h[t]=0;
	que.push(t);
	while(!que.empty()) {
		now=que.front();
		que.pop();
		for(i=head[now]; i; i=Next[i])
			if(w[i^1]&&h[to[i]]>h[now]+1)
				h[to[i]]=h[now]+1,que.push(to[i]);
	}
	return h[s]!=inf;
}
inline void push(int now) { //推送
	int d,i;
	for(i=head[now]; i; i=Next[i])
		if(w[i]&&h[to[i]]+1==h[now]) {
			d=min(e[now],w[i]);
			w[i]-=d;
			w[i^1]+=d;
			e[now]-=d;
			e[to[i]]+=d;
			if(to[i]!=s&&to[i]!=t&&!inq[to[i]])
				pque.push(to[i]),inq[to[i]]=1;
			if(!e[now])//已经推送完毕可以直接退出
				break;
		}
}
inline void relabel(int now) { //重贴标签
	int i;
	h[now]=inf;
	for(i=head[now]; i; i=Next[i])
		if(w[i]&&h[to[i]]+1<h[now])
			h[now]=h[to[i]]+1;
	return;
}
inline int hlpp() {
	int now,d,i,x;
	if(!bfs())//s和t不连通 
		return 0;
	h[s]=n;
	memset(gap,0,sizeof(int)*(n<<1));
	for(i=1; i<=n; i++)
		if(h[i]<inf)
			++gap[h[i]];
	for(x=head[s]; x; x=Next[x])
		if(d=w[x]) {
			w[x]-=d;
			w[x^1]+=d;
			e[s]-=d;
			e[to[x]]+=d;
			if(to[x]!=s&&to[x]!=t&&!inq[to[x]])
				pque.push(to[x]),inq[to[x]]=1;
		}
	while(!pque.empty()) {
		inq[now=pque.top()]=0;
		pque.pop();
		push(now);
		if(e[now]) {
			if(!--gap[h[now]])//gap优化，因为当前节点是最高的所以修改的节点一定不在优先队列中，不必担心修改对优先队列会造成影响 
				for(i=1; i<=n; i++)
					if(i!=s&&i!=t&&h[i]>h[now]&&h[i]<n+1)
						h[i]=n+1;
			relabel(now);
			++gap[h[now]];
			pque.push(now);
			inq[now]=1;
		}
	}
	return e[t];
}
signed main() {
	int u,v,w;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	while(m--) {
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	printf("%d\n",hlpp());
	return 0;
}

玄学+剪枝优化：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct hlpp {
		struct Edge {
			int to,rev;
			ll c;
			Edge(int to,ll c,int rev):to(to),rev(rev),c(c) {}
		};
		int n,m,s,t;
		int maxh,maxgaph,workcnt;
		vector<vector<Edge> >vec;
		vector<ll>ov;
		vector<int>h;
		vector<int>cur;
		vector<int>ovList,ovNxt;
		vector<int>gap,gapPrv,gapNxt;
		hlpp(int n, int s, int t): n(n), s(s), t(t), maxh(0), maxgaph(0), workcnt(0),
			vec(n+1), ov(n+1), h(n+1), cur(n+1),
			ovList((n+1), -1), ovNxt(n+1, -1),
			gap((n+1), -1), gapPrv(n+1, -1), gapNxt(n+1, -1) {}
		void add(int u, int v, ll c) {
			vec[u].push_back(Edge(v, c, vec[v].size()));
			vec[v].push_back(Edge(u, 0, vec[u].size()-1));
		}
		ll getMaxFlow() {
			globalRelabel();
			for(auto &e: vec[s]) if(e.c) {
					pushFlow(s, e, e.c);
					maxh = max(maxh, h[e.to]);
				}
			for(; maxh >= 0; --maxh) {
				while(~ovList[maxh]) {
					int x = ovList[maxh];
					ovList[maxh] = ovNxt[x];
					discharge(x);
					if(workcnt > (n<<2))  globalRelabel();
				}
			}
			return ov[t];
		}
	private:	
		void globalRelabel() {
			workcnt = maxh = maxgaph = 0;
			for(int i=0;i<=n;++i) {
				gapPrv[i]=gapNxt[i]=gap[i]=ovList[i]=ovList[i]=-1;
				cur[i]=0;	h[i]=n;
			}
			h[t] = 0;
			queue<int> que;
			que.push(t);
			int x;
			while(!que.empty()) {
				x = que.front();
				que.pop();
				for(auto &e: vec[x]) {
					if(h[e.to] == n && e.to != s && vec[e.to][e.rev].c > 0) {
						setHeight(e.to, h[x]+1);
						que.push(e.to);
					}
				}
			}
		}
		void pushFlow(int from, Edge &e, ll flow) {
			if(!ov[e.to] && e.to != t) {
				ovNxt[e.to] = ovList[h[e.to]];
				ovList[h[e.to]] = e.to;
			}
			e.c -= flow;
			vec[e.to][e.rev].c += flow;
			ov[from] -= flow;
			ov[e.to] += flow;
		}
		void setHeight(int x, int newh) {
			if(~gapPrv[x]) {
				if(gapPrv[x] == x) {
					gapPrv[gapNxt[x]] = gapNxt[x];
					gap[h[x]] = gapNxt[x];
				} else {
					gapNxt[gapPrv[x]] = gapNxt[x];
					if(~gapNxt[x])  gapPrv[gapNxt[x]] = gapPrv[x];
				}
			}
			if((h[x] = newh) >= n)  return ; // ignore the case of h >= n
			maxgaph = max(maxgaph, h[x]);
			if(ov[x] > 0) {
				maxh = max(maxh, h[x]);
				ovNxt[x] = ovList[h[x]];
				ovList[h[x]] = x;
			}
			if(~(gapNxt[x] = gap[h[x]]))  gapPrv[gapNxt[x]] = x;
			gap[h[x]] = gapPrv[x] = x;
		}
		void discharge(int x) {
			int nh = n, sz = vec[x].size();
			for(int i = cur[x]; i < sz; ++i) {
				auto &e = vec[x][i];
				if(e.c > 0) {
					if(h[x] == h[e.to]+1) {
						pushFlow(x, e, min(ov[x], e.c));
						if(ov[x] == 0) {
							cur[x] = i;
							return ;
						}
					} else nh = min(nh, h[e.to]+1);
				}
			}
			for(int i = 0; i < cur[x]; ++i) {
				auto &e = vec[x][i];
				if(e.c > 0) {
					nh = min(nh, h[e.to]+1);
				}
			}
			cur[x] = 0;
			++workcnt;
			if(~gapNxt[gap[h[x]]])  setHeight(x, nh);
			else {
				int oldh = h[x];
				for(int i = oldh; i <= maxgaph; ++i) {
					for(int j = gap[i]; ~j; j = gapNxt[j])  h[j] = n;
					gap[i] = -1;
				}
				maxgaph = oldh-1;
			}
		}
};
int main() {
	int n,m,s,t,u,v; ll w;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	hlpp ac(n,s,t);
	while(m--) {
		scanf("%d%d%lld",&u,&v,&w);
		ac.add(u,v,w);
	}
	printf("%lld\n",ac.getMaxFlow());
	return 0;
}