preface

There should be no cancer. People will go to cards \ (\ textsf{Dinic} \) and \ (\ textsf{ISAP} \).

Maximum flow

First, define what we want to do - find the maximum flow.

Then use the most common analogy: the source point is the water delivery from the waterworks, and all the water output from the source point needs to flow into the sewage treatment plant, but the water pipe has a flow limit.

Then there is a very \ (\ textsf{naive} \) idea, which is to violently increase the water pressure and crazy irrigation from the source point. Anyway, the amount of water at the source point is unlimited, and no more flow can be obtained from irrigation to the sink point. At this time, there is no free flow path from the source point to the sink point, that is, there is no augmented path. According to the augmented path theorem, the flow at this time is the maximum flow.

Then two people said, wouldn't it be OK for me to go out directly from the source point along the Zengguang road? Each time I expand one path to the sink point, I will certainly be able to find the maximum flow.

These two people are \ (\ textsf{L.R.Ford,Jr.} \) and \ (\ textsf{D.R.Fulkerson} \), which are the \ (\ textsf{Ford – Fulkerson} \) algorithm proposed by them (more accurately, \ (\ textsf{Ford – Fulkerson} \) method), and \ (\ textsf {Edmonds Karp, dinic, ISAP} \) are their specific implementation methods.

This method is still based on the path expansion, and the flow conservation needs to be guaranteed in the whole process, so some people think it's too bad.

Pre flow propulsion

First, two new ideas are put forward:

1. Abandon "Zengguang road" and directly maintain point-to-point
2. In the process of finding the maximum flow, the flow conservation is temporarily ignored, and the flow conservation is eliminated*

Consider maintaining the flow at each point, ignoring the conservation of flow in the process, filling the edge violently, and then let the node maintain the flow. Using the above analogy, build an infinite water storage tank in each house, then you can maintain the excess flow at each point, and then transfer the flow to other nodes.

The specific process is as follows:

1. Fill up the points connected to the source point.
2. Every update can send out the excess traffic until there is no excess traffic at all points except the source and sink points
3. At this time, the excess flow of the sink is the maximum flow

However, this process is extremely imperfect. Since the flow can flow back from the opposite side after passing through the positive side, it will flow back directly according to this process.

When learning \ (\ textsf{Dinic} \), we know that in order to prevent backflow, we assign a top mark to each point. Here, follow this method to allocate the height from the sink point to the source point. For a point \ (u \), only the excess flow can be distributed to the connected points \ (v \) that meet \ (h(u) = h(v) + 1 \).

At this time, we have completed a reasonable push (\ (\ bf{push} \)), but whether it is \ (\ textsf{Dinic} \) or \ (\ textsf{ISAP} \), we need to adjust the top standard to find all the expansion paths. Here, in order to make the excess flow flow flow out enough, we need a process of re labeling (\ (\ bf{relable} \).

For a point \ (u \), if the current label has pushed as many streams as possible, but there is still excess traffic left, find a point \ (v \) with the lowest height from all the connected points, and then make \ (h(u) \leftarrow h(v) + 1 \).

Finally, in order to prevent the flow from the source point from directly returning to the source point, we set the initial height of the source point to \ (n \).

It can be found that the last excess flow that cannot be pushed will return to the source along the opposite edge, and the final graph shape is also flow balanced.

This is \ (\ textsf {push release} \) preflow propulsion. The complexity \ (\ mathcal{O} (n^2m) \) is the same as the commonly used \ (\ textsf{Dinic} \).

Rearrange your thinking:

1. Fill up the excess flow of the point connected with the source point.
2. For each overflow point \ (u \), push the flow to the connected point \ (v \) satisfying \ (h(u) = h(v) + 1 \).
3. If all the points that can be pushed by \ (u \) still overflow after being pushed, update the height of \ (u \) to the height of the lowest of all the points connected with \ (u \) plus one.
4. After the flow is balanced, the excess flow of the sink is the maximum flow.

The code size is similar to the maximum stream of other (except HLPP), and the constant is slightly larger.

But it's easier to understand and write.

Code :

int head[N],ecnt = -1;
struct Edge {
	int nxt,to,cap;
}e[M << 1];
inline void AddEdge(int st,int ed,int cap) {
	e[++ecnt] = (Edge) {head[st],ed,cap},head[st] = ecnt;
	e[++ecnt] = (Edge) {head[ed],st,0},head[ed] = ecnt;
}

int n,m,s,t;
int h[N];
ll ex[N];

inline void init() {
	repg(i,s) {
		int v = e[i].to;
		ex[v] += e[i].cap,ex[s] -= e[i].cap;
		e[i ^ 1].cap = e[i].cap,e[i].cap = 0;
	}
	h[s] = n;
}

inline bool push(int ed) {
	const int u = e[ed ^ 1].to,v = e[ed].to;
	int f = std::min(ex[u],(ll)e[ed].cap);
	ex[u] -= f,ex[v] += f;
	e[ed].cap -= f,e[ed ^ 1].cap += f;
	return ex[u];
}

inline void relable(int u) {
	h[u] = INF;
	repg(i,u) if(e[i].cap)
		h[u] = std::min(h[u],h[e[i].to]);
	++h[u];
}

inline ll PushRelable() {
	bool flag = 1;
	init();
	while(flag) {
		flag = 0;
		rep(u,1,n) if(ex[u] > 0 && u != s && u != t) {
			flag = 1;
			bool re = 1;
			repg(i,u) {
				if(e[i].cap && h[u] == h[e[i].to] + 1)
					re &= push(i);
				if(!re) break;
			}	
			if(re) relable(u);
		}
	}
	return ex[t];
}

HLPP

\(\ mathsf{HLPP} \), the full name is the highest label pre flow propulsion.

Through the above process, we find that it is better to send out the excess traffic of the node with high label first. Then, maintain a large root heap, maintain the largest updatable \ (u \) of \ (h(u) \), and select the top element to push the flow each time.

Then, in order not to take \ (\ log \), directly open \ (2n - 1 \) barrels to maintain the height.

However, it can be found from the above that even if the final excess flow does not flow back to the source point, it will not affect the maximum flow, so only open \ (n \) barrels.

It seems that HLPP also has current arc optimization, but we won't.

You can see the implementation of God \ (\ mathrm {\ color {black} m} {\ color {red} in \ _25} \): \(\texttt{Link}\)

Complexity \ (\ mathcal{O} (n^2\sqrt{m}) \).

How to put it... Even in the normal version, the maximum flow is very fast.

Template: \(\texttt{Link}\)

Code :

int head[N],ecnt = -1;
struct Edge {
	int nxt,to,cap;
}e[M << 1];
inline void AddEdge(int st,int ed,int cap) {
	e[++ecnt] = (Edge) {head[st],ed,cap},head[st] = ecnt;
	e[++ecnt] = (Edge) {head[ed],st,0},head[ed] = ecnt;
}

int n,m,s,t;
int h[N],ex[N];
int gap[N];
std::stack<int> buc[N];
int mxht;// max height

inline bool push(int u) {
	bool pre = (u == s);
	repg(i,u) {
		const int v = e[i].to;
		if(!e[i].cap || (!pre && h[u] != h[v] + 1))
			continue;
		int tf = pre ? e[i].cap : std::min(e[i].cap,ex[u]);
		if (v != s && v != t && !ex[v])
			buc[h[v]].push(v),mxht = std::max(mxht,h[v]);
		ex[u] -= tf,ex[v] += tf;
		e[i].cap -= tf,e[i ^ 1].cap += tf;
		if(!ex[u]) return 0;
	}
	return 1;
}

inline void relable(int u) {
	h[u] = INF;
	repg(i,u) if(e[i].cap)
		h[u] = std::min(h[u],h[e[i].to]);
	if(++h[u] < n) {
		buc[h[u]].push(u);
		mxht = std::max(mxht,h[u]);
		++gap[h[u]];
	}
}

bool bfs() {
	mems(h,63),h[t] = 0;
	std::queue<int> q;q.push(t);
	while(!q.empty()) {
		int u = q.front();q.pop();
		repg(i,u) {
			int v = e[i].to;
			if(e[i ^ 1].cap && h[v] > h[u] + 1) {
				h[v] = h[u] + 1;
				q.push(v);
			}
		}
	}
	return h[s] != 0x3f3f3f3f;
}

inline int GetHmax() {
	while(buc[mxht].empty() && mxht > -1)
		--mxht;
	return (~mxht) ? buc[mxht].top() : 0;
}

inline int HLPP() {
	if(!bfs()) return 0;
	mems(gap,0);
	rep(i,1,n) if(h[i] != 0x3f3f3f3f)
		++gap[h[i]];
	h[s] = n,push(s);
	int u;
	while((u = GetHmax())) {
		buc[mxht].pop();
		if(push(u)) {
			if(!--gap[h[u]]) {
				rep(i,1,n) if(i != s && i != t && h[i] > h[u] && h[i] < n + 1)
					h[i] = n + 1;
			}
			relable(u);
		}
	}
	return ex[t];
}