网络流小记

基本定义：

• 网络：一张有向图。

• 流量：经过一条边的流的大小，一条边 \((u,v)\) 的流量记为 \(flow(u,v)\)， 一个网络的流量定义为 \(∑f(s,x)\)。

• 容量：一条边的流量上限，一条边 \((u,v)\) 的容量记为 \(cap(u,v)\)。

• 费用：经过一条边单位流量的所需费用，一条边 \((u,v)\) 的费用记为 \(cost(u,v)\)。

• 源点：所有流的起始点, 记为 \(s\)。

• 汇点：所有流的终止点，记为 \(t\)。

• 割：是网络的一个划分， 一个割 {\(S, T\)} 的容量定义为 \(||S, T|| = \sum_{u \in S} \sum_{v \in T} cap(u, v)\)。

• 残量网络：每条边剩余可走的流量组成的网络。

网络流的性质：

1. 斜对称性：\(flow(u,v) = -flow(v,u)\)

2. 流量守恒：\(\sum_{u \ne x, t\ne y} flow(u, x) = \sum flow(y,u)\)

3. 容量限制： \(flow(u,v) \le cap(u,v)\)

一些定理：

增广路定理：

增广路：在残量网络中的一条 \(s\) 到 \(t\) 的路径，满足路径上的残量均大于 \(0\)。

一个流为最大流当且仅当网络中没有增广路。

最大流最小割定理：

对于任意网络，最大流 \(f\) 和最小割 \(\{S, T\}\) 总是满足 \(|f| = ||S, T||\)。

证明可见 OI-WIKI。

EK 算法：

对于求一张图的最大流，我们考虑引入反向边的概念。

由上面的定理，我们可以得到以下算法：

1. 在残量网络上找一条增广路，将这条路径上的流大小记为 \(flow\)

2. 将路径上的所有边加上 \(flow\)，反向边减掉 \(flow\)。

注意：增广路可以经过反向边！

经过反向边相当于做返回操作，这也是 EK 算法的关键之处。

时间复杂度 \(O(nm^2)\)。

Dinic 算法：

考虑优化上面的算法，我们将原图进行分层，从源点开始，按于源点的距离分层。

做完分层后，像 EK 一样在分层图中找增广路，但是一次可以找多条。

前者用 bfs 实现，后者用 dfs 实现。

code:

namespace Dinic{
	struct edge{
		int v, next, cap, flow;
	}edges[M << 1];
	int head[N], idx = 1;
	int cur[N], dep[N];
	int maxflow = 0;
	
	void add_edge(int u, int v, int cap){
		edges[++idx] = {v, head[u], cap, 0};
		head[u] = idx;
	}
	bool bfs(){
		queue<int>Q;
		memset(dep, 0, sizeof dep);
		dep[s] = 1, Q.push(s);
		while(!Q.empty()){
			int u = Q.front(); Q.pop();
			for(int i = head[u]; i; i = edges[i].next){
				int v = edges[i].v;
				if(!dep[v] && (edges[i].cap > edges[i].flow)){
					dep[v] = dep[u] + 1;
					Q.push(v);
				}
			}
		} 
		return dep[t];
	}
	int dfs(int u, int flow){
		if(u == t || (!flow)) return flow;
		int ret = 0;
		for(int& i = cur[u]; i; i = edges[i].next){
			int v = edges[i].v, d;
			if((dep[v] == dep[u] + 1) && (d = dfs(v, min(flow - ret, edges[i].cap - edges[i].flow)))){
				ret += d; edges[i].flow += d; edges[i ^ 1].flow -= d;
				if(ret == flow) return flow;
			}
		}
		return ret; 
	}
	void dinic(){
		while(bfs()){
			memcpy(cur, head, sizeof(int) * (n + 1));
			maxflow += dfs(s, INF);
		}
	}
}

一些例题：

this

（有待修缮）