網絡流學習筆記

前言

網絡流中板子并不難，真正難的是復雜度的證明還有一大堆的二級結論，本筆記主要記錄學習路上遇到的各種網絡流技巧與結論，相關證明可以去 OI Wiki 看。

最大流 & 最小割

首先有一個基本定理：最大流等價于最小割。

Edmonds–Karp 算法

簡稱 EK 算法，是最最基礎的網絡流算法，也是最慢的。

單次增廣的過程：先 BFS 進行分層，然后從匯點回溯回去，復雜度為 \(O(|E|)\)。

而增廣總輪數為 \(O(|V||E|)\)，總復雜度為 \(O(|V||E|^2)\)。

namespace EK {
	int pa[N],dep[N],flow[N];
	template<const int N,const int M>struct CFS {
		int tot,h[N];
		struct edge {
			int u,v,c,f,nxt;
			edge(int u=0,int v=0,int c=0,int f=0,int nxt=-1):u(u),v(v),c(c),f(f),nxt(nxt) {}
		} e[M];

		edge &operator [](int i) { return e[i]; }

		void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

		void att(int u,int v,int c=0,int f=0) { e[++tot]=edge(u,v,c,f,h[u]),h[u]=tot; }

		void con(int u,int v,int c) { att(u,v,c),att(v,u); }

	};
	CFS<N,M<<1> g;

	void Build(int n,int m) {
		g.Init(n);
		FOR(i,1,m) {
			int u,v,c;
			cin>>u>>v>>c,g.con(u,v,c);
		}
	}

	bool BFS(int S,int T) {
		queue<int> q;
		RCL(dep+1,0,int,n),flow[S]=INF,dep[S]=1,q.push(S);
		while(!q.empty()&&!dep[T]) {
			int u(q.front());
			q.pop();
			EDGE(g,i,u,v)if(g[i].f<g[i].c&&!dep[v])
				pa[v]=i,flow[v]=min(flow[u],g[i].c-g[i].f),dep[v]=dep[u]+1,q.push(v);
		}
		return dep[T];
	}

	ll Max_Flow(int S,int T) {
		ll Flow(0);
		while(BFS(S,T)) {
			Flow+=flow[T];
			for(int u(T); u^S; u=g[pa[u]].u)g[pa[u]].f+=flow[T],g[pa[u]^1].f-=flow[T];
		}
		return Flow;
	}

}

Dinic 算法

Dinic 算法給人最大的印象就是比 EK 算法多了一個多路增廣。同時為了實現多路增廣，我們還需要給它加入當前弧優化，這個優化在歐拉路徑中也有，就是為了不讓 DFS 時重復訪問同一條邊，我們把它直接刪掉之類的。

過程：單輪增廣先進行一遍 BFS，再進行一遍 DFS 多路增廣求阻塞流，這一過程復雜度是 \(O(|E||V|)\)。

而總輪數不會超過 \(O(|V|)\)，總復雜度 \(O(|V|^2|E|)\)。

一張圖中，任意一個連通子圖中 \(|E| \ge |V| - 1\)，所以我們認為 \(|E| \ge |V|\)，這樣來看 Dinic 算法的時間復雜度優于 EK 算法。

namespace Dinic {
	int dep[N];
	template<const int N,const int M>struct CFS {
		int tot,h[N],_h[N];
		struct edge {
			int v,c,f,nxt;
			edge(int v=0,int c=0,int f=0,int nxt=-1):v(v),c(c),f(f),nxt(nxt) {}
		} e[M];

		edge &operator [](int i) { return e[i]; }

		void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

		void Copy(int n) { CPY(_h+1,h+1,int,n); }

		void att(int u,int v,int c=0,int f=0) { e[++tot]=edge(v,c,f,h[u]),h[u]=tot; }

		void con(int u,int v,int c) { att(u,v,c),att(v,u); }

	};
	CFS<N,M<<1> g;

	void Build(int n,int m) {
		g.Init(n);
		FOR(i,1,m) {
			int u,v,c;
			cin>>u>>v>>c,g.con(u,v,c);
		}
	}

	bool BFS(int S,int T) {
		queue<int> q;
		RCL(dep+1,0,int,n),dep[S]=1,q.push(S);
		while(!q.empty()&&!dep[T]) {
			int u(q.front());
			q.pop();
			EDGE(g,i,u,v)if(g[i].f<g[i].c&&!dep[v])dep[v]=dep[u]+1,q.push(v);
		}
		return dep[T];
	}

	int DFS(int u,int T,int flow) {
		if(u==T||!flow)return flow;
		int ret(0),d(0);
		_EDGE(g,i,u,v)if(dep[v]==dep[u]+1&&(d=DFS(v,T,min(flow-ret,g[i].c-g[i].f)))) {
			g[i].f+=d,g[i^1].f-=d,ret+=d;
			if(ret==flow)return ret;
		}
		return ret;
	}

	ll Max_Flow(int n,int S,int T) {
		ll Flow(0);
		while(BFS(S,T))
			g.Copy(n),Flow+=DFS(S,T,INF);
		return Flow;
	}

}

特殊情況

對于單位容量的網絡：單輪增廣的時間復雜度為 \(O(|E|)\)，增廣輪數是 \(O(\min{(|E|^{\frac{1}{2}},|V|^{\frac{2}{3}})})\)，故總復雜度為 \(O(|E|\min{(|E|^{\frac{1}{2}},|V|^{\frac{2}{3}})})\)。

如果單位容量的網絡滿足除源匯點外每個節點 \(u\) 都滿足 \(deg_{in}(u) = deg_{out}(u) = 1\)，那么它的增廣輪數降到 \(O(|V|^{\frac{1}{2}})\)。

由此，我們可以用 Dinic 算法來求二分圖最大匹配。

費用流

這部分是基于最大流算法的，故請先熟悉最大流算法的板子。

SSP 算法 & zkw 費用流

很容易想到用最短路配合 Dinic、EK 之類的算法來進行費用流的求解，其中用 Dinic 的叫做 zkw 費用流。

不過圖上的反向邊權會取原邊的相反數，所以有負邊權，不能用 Dijkstra，那么就只能用 Bellman-Ford 算法。

不過時間復雜度為 \(O(nmf)\)，其中 \(f\) 為網絡最大流的值。

namespace SSP {
	bool vis[N];
	int dis[N];
	template<const int N,const int M>struct CFS {
		int tot,h[N],_h[N];
		struct edge {
			int v,w,c,f,nxt;
			edge(int v=0,int w=0,int c=0,int f=0,int nxt=-1):v(v),w(w),c(c),f(f),nxt(nxt) {}
		} e[M];

		edge &operator [](int i) { return e[i]; }

		void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

		void Copy(int n) { CPY(_h+1,h+1,int,n); }

		void att(int u,int v,int w,int c=0) { e[++tot]=edge(v,w,c,0,h[u]),h[u]=tot; }

		void con(int u,int v,int w,int c) { att(u,v,w,c),att(v,u,-w); }

	};
	CFS<N,M<<1> g;

	bool SPFA(int S,int T) {
		queue<int> q;
		RCL(dis+1,INF,int,n),dis[S]=0,vis[S]=1,q.push(S);
		while(!q.empty()) {
			int u(q.front());
			q.pop(),vis[u]=0;
			EDGE(g,i,u,v)if(dis[v]>dis[u]+g[i].w&&g[i].c>g[i].f) {
				dis[v]=dis[u]+g[i].w;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
		return dis[T]<INF;
	}

	void Build(int n,int m) {
		g.Init(n);
		FOR(i,1,m) {
			int u,v,c,w;
			cin>>u>>v>>c>>w,g.con(u,v,w,c);
		}
	}

	int DFS(int u,int T,int flow,int &cost) {
		if(u==T||!flow)return flow;
		int ret(0),d(0);
		vis[u]=true;
		_EDGE(g,i,u,v)
			if(!vis[v]&&dis[v]==dis[u]+g[i].w&&(d=DFS(v,T,min(flow-ret,g[i].c-g[i].f),cost))) {
				g[i].f+=d,g[i^1].f-=d,ret+=d,cost+=d*g[i].w;
				if(ret==flow)return vis[u]=false,ret;
			}
		return vis[u]=false,ret;
	}

	Pii MCMF(int n,int S,int T) {
		int Flow(0),Cost(0);
		while(SPFA(S,T))g.Copy(n),Flow+=DFS(S,T,INF,Cost);
		return Pii(Flow,Cost);
	}

}

Primal-Dual 原始對偶算法

不能用 Dijskstra 怎么辦呢？Johnson 全源最短路徑算法了解一下，用勢能處理負邊權，只要先跑一遍 Bellman-Ford，然后用勢能在邊權上做一點手腳即可。

但是如果每次都跑一遍 Bellman-Ford 的話，復雜度又退化回去了，我們可以在勢能上加上 Dijkstra 跑出來的最短距離，這樣就解決了。

時間復雜度 \(O(nm+m\log_2{m}f)\)。

namespace PD {
	bool vis[N];
	int h[N],dis[N];
	template<const int N,const int M>struct CFS {
		int tot,h[N],_h[N];
		struct edge {
			int v,w,c,f,nxt;
			edge(int v=0,int w=0,int c=0,int f=0,int nxt=-1):v(v),w(w),c(c),f(f),nxt(nxt) {}
		} e[M];

		edge &operator [](int i) { return e[i]; }

		void Init(int n) { RCL(h+1,-1,int,n),tot=-1; }

		void Copy(int n) { CPY(_h+1,h+1,int,n); }

		void att(int u,int v,int w,int c=0) { e[++tot]=edge(v,w,c,0,h[u]),h[u]=tot; }

		void con(int u,int v,int w,int c) { att(u,v,w,c),att(v,u,-w); }

	};
	CFS<N,M<<1> g;

	void Build(int n,int m) {
		g.Init(n);
		FOR(i,1,m) {
			int u,v,c,w;
			cin>>u>>v>>c>>w,g.con(u,v,w,c);
		}
	}

	void SPFA(int S,int T) {
		queue<int> q;
		RCL(h+1,INF,int,n),h[S]=0,vis[S]=1,q.push(S);
		while(!q.empty()) {
			int u(q.front());
			q.pop(),vis[u]=0;
			EDGE(g,i,u,v)if(h[v]>h[u]+g[i].w&&g[i].c>g[i].f) {
				h[v]=h[u]+g[i].w;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}

	bool Dij(int S,int T) {
		priority_queue<Pii,vector<Pii>,greater<Pii> > q;
		RCL(vis+1,false,bool,n),RCL(dis+1,INF,int,n),dis[S]=0,q.push({0,S});
		while(!q.empty()) {
			int u(q.top().Se);
			q.pop();
			if(vis[u])continue;
			vis[u]=1;
			EDGE(g,i,u,v)if(dis[v]>dis[u]+(h[u]-h[v]+g[i].w)&&g[i].c>g[i].f)
				dis[v]=dis[u]+(h[u]-h[v]+g[i].w),q.push({dis[v],v});
		}
		return dis[T]<INF;
	}

	int DFS(int u,int T,int flow,int &cost) {
		if(u==T||!flow)return flow;
		int ret(0),d(0);
		vis[u]=true;
		_EDGE(g,i,u,v)
			if(!vis[v]&&g[i].c>g[i].f&&dis[v]==dis[u]+(h[u]-h[v]+g[i].w)) {
				d=DFS(v,T,min(flow-ret,g[i].c-g[i].f),cost),g[i].f+=d,g[i^1].f-=d,ret+=d,cost+=d*g[i].w;
				if(ret==flow)return vis[u]=false,ret;
			}
		return vis[u]=false,ret;
	}

	Pii MCMF(int n,int S,int T) {
		int Flow(0),Cost(0);
		SPFA(S,T);
		while(Dij(S,T)) {
			RCL(vis+1,false,bool,n),g.Copy(n),Flow+=DFS(S,T,INF,Cost);
			FOR(i,1,n)if(dis[i]<INF)h[i]+=dis[i];
		}
		return Pii(Flow,Cost);
	}

}

模擬費用流

我們可以用費用流的思路來想貪心等算法，或者說用貪心等算法來做費用流。

題目

二分圖相關

飛行員配對方案問題

明顯的二分圖問題，轉成最大流用 Dinic 求解即可，時間復雜度懶得打了。

最小路徑覆蓋問題

在二分圖里也有類似的題目，套路是拆點，然后源點連出點，出點連入點，入點連匯點。

方格取數問題

這題先要找找性質：我們如果把相鄰的點全部連起來，那么會得到一個二分圖。我們左部連源點，右部連匯點，這些邊的流量就是自己的權值，中間連相鄰點的邊流量都是無限。

最長不下降子序列問題

最小路徑覆蓋問題結合 DP。

問題 1：DP。
問題 2：建圖部分拆點限制流量為 \(1\)。

然后把源點連向 DP 值為 \(1\) 的，DP 值為最大值的連向匯點，流量都為 \(1\)。

對于 \(i<j\)，如果滿足 \(a_i \le a_j \land f_j = f_{i} + 1\)，那么 \(i\) 連向 \(j\)。
問題 3：把限制 \(1\) 和 \(n\) 流量的邊都改為 \(\inf\)。