[洛谷P4722]【模板】最大流 加强版 / 预流推进

会$TLE$。。。

C++ Code：（HLPP）

#pragma GCC optimize(3)

#pragma GCC optimize("unroll-loops")

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#define maxn 1210

#define maxm 120010

const int inf = 0x3f3f3f3f;

inline int min(int a, int b) {return a < b ? a : b;}

namespace Network_Flow {

	int st, ed, MF, n;

	int head[maxn], cnt = 2;

	struct Edge {

		int to, nxt, w;

	} e[maxm << 1];

	inline void addE(int a, int b, int c) {

		e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;

		e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1;

		cnt += 2;

	}

	bool inq[maxn];

	int GAP[maxn << 1], h[maxn];

	int prs[maxn];

	struct cmp {

		inline bool operator () (int a, int b) const {return h[a] < h[b];}

	};

	std::priority_queue<int, std::vector<int>, cmp> q;

	inline bool N(int p) {return p != st && p != ed;}

	inline void Push(int u) {

		const int H = h[u] - 1;

		for (register int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (e[i].w && h[v] == H) {

				int w = min(prs[u], e[i].w);

				e[i].w -= w, e[i ^ 1].w += w;

				prs[u] -= w, prs[v] += w;

				if (v != st && v != ed && !inq[v]) {

					q.push(v);

					inq[v] = true;

				}

				if (!prs[u]) return ;

			}

		}

	}

	inline void Gap(int H) {

		for (register int i = 1; i <= n; i++) if (N(i) && H < h[i] && h[i] <= n) h[i] = n + 1;

	}

	namespace BFS {

		int Q[maxn], H, T;

		inline bool bfs() {

			memset(h, 0x3f, sizeof h);

			h[Q[H = T = 0] = ed] = 1;

			while (H <= T) {

				int u = Q[H++];

				for (int i = head[u]; i; i = e[i].nxt) {

					int v = e[i].to;

					if (e[i ^ 1].w && h[v] > h[u] + 1) {

						h[v] = h[u] + 1;

						Q[++T] = v;

					}

				}

			}

			return h[ed] != inf;

		}

	}

	inline void relabel(int u) {

		int &H = h[u] = inf;

		for (register int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (e[i].w && h[v] + 1 < H) H = h[v] + 1;

		}

	}

	inline void HLPP(int __S, int __T) {

		st = __S, ed = __T;

		if (!BFS::bfs()) return ;

		h[st] = n;

		for (register int i = 1; i <= n; i++) if (h[i] < inf) GAP[h[i]]++;

		for (register int i = head[st]; i; i = e[i].nxt) {

			int v = e[i].to, &w = e[i].w;

			if (!w) continue;

			e[i ^ 1].w += w, prs[st] -= w, prs[v] += w;

			w = 0;

			if (v != ed && !inq[v]) {

				q.push(v);

				inq[v] = true;

			}

		}

		while (!q.empty()) {

			int u = q.top(); q.pop();

			inq[u] = false; Push(u);

			if (!prs[u]) continue;

			if (!--GAP[h[u]]) for (register int i = 1; i <= n; i++) if (i != st && i != ed && h[u] < h[i] && h[i] <= n) h[i] = n + 1; //Gap(h[u]);

			relabel(u); GAP[h[u]]++;

			q.push(u); inq[u] = true;

		}

		MF = prs[ed];

	}

	inline void clear() {

		memset(head, 0, sizeof head); cnt = 2;

		memset(GAP, 0, sizeof GAP); memset(prs, 0, sizeof prs);

		while (!q.empty()) q.pop();

		MF = 0;

	}

}

#define read() R::READ()

#include <cctype>

namespace R {

	int x;

	#ifdef ONLINE_JUGER

	#define M 1 << 25

	char op[M], *ch;

	inline void init() {fread(ch = op, 1, M, stdin);}

	inline int READ() {

		while (isspace(*ch)) ch++;

		for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);

		return x;

	}

	#undef M

	#else

	char ch;

	inline int READ() {

		ch = getchar();

		while (isspace(ch)) ch = getchar();

		for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);

		return x;

	}

	#endif

}

int n, m, st, ed;

int main() {

	#ifdef ONLINE_JUGER

	R::init();

	#endif

	Network_Flow::n = read(), m = read(), st = read(), ed = read();

	for (register int i = 0, a, b, c; i < m; i++) {

		a = read(), b = read(), c = read();

		Network_Flow::addE(a, b, c);

	}

	Network_Flow::HLPP(st, ed);

	printf("%d\n", Network_Flow::MF);

	return 0;

}