网络流笔记

增广路#

ek 模板：

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=205,M=5005;
int n,m,s,t,cnt=1,head[N],pre[N],mf[N];
/*
mf：当前增广路可通过水流
*/
struct edge{
	int nxt,to,w;
}e[2*M];
void add(int u,int v,int w){
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
bool bfs(){
	memset(mf,0,sizeof mf);
	queue<int>q;
	q.push(s);
	mf[s]=1e9;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(mf[v]==0&&e[i].w){
				mf[v]=min(mf[u],e[i].w);
				pre[v]=i;
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
ll ek(){
	ll fl=0;
	while(bfs()){
		int v=t;
		while(v!=s){
			int i=pre[v];
			e[i].w-=mf[t];
			e[i^1].w+=mf[t];
			v=e[i^1].to;
		}
		fl+=mf[t];
	}
	return fl;
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,0);
	}
	cout<<ek();
	return 0;
}

cpp

Dinic 模板：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=5005;
int n,m,s,t,head[M],tot=1,d[M],cur[M];
struct edge{
	int v,nxt;
	ll flow;
}e[2*M];
void add(int u,int v,int w){
	e[++tot]={v,head[u],w},head[u]=tot;
}
bool bfs(){
	memset(d,0,sizeof d);
	memcpy(cur,head,sizeof head);
	queue<int>q;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].nxt){
			int v=e[i].v;
			if(!d[v]&&e[i].flow){
				d[v]=d[u]+1;
				if(v==t)return true;
				q.push(v);
			}
		}
	}
	return false;
}
ll dfs(int u,ll flow){
	if(u==t||!flow)return flow;
	ll rest=flow;
	for(int &i=cur[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(d[v]==d[u]+1&&e[i].flow){
			ll k=dfs(v,min(rest,e[i].flow));
			if(!k)d[v]=0;
			e[i].flow-=k,e[i^1].flow+=k;
			if(!(rest-=k))break;
		}
	}
	return flow-rest;
}
ll dinic(){
	ll maxflow=0;
	while(bfs())maxflow+=dfs(s,INT_MAX);
	return maxflow;
}
int main(){
	memset(head, -1, sizeof(head));
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w),add(v,u,0);
	}
	cout<<dinic();
	return 0;
}

cpp

:::warning[请注意]{open} 本文章使用了 AI 辅助编写，请谨慎鉴别。 :::

Part. 1 网络流的定义#

1.1 流网络#

一个流网络是一个四元组 $N=(G,c,s,t)$ ，其中：

$G=(V,E)$ 是一个无自环有向图。
$c:E\mapsto[0,+\infty)$ 是容量函数， $c(u,v)\geqslant0$ 。
$s\in V$ 是源点， $t\in V$ 是汇点， $s\ne t$ 。

1.2 流#

一个流是函数 $f:E\to\mathbb{R}_{\geqslant0}$ ，满足：

(1) 容量约束：对每条边 $(u,v)\in E$ ， $0\leqslant f(u,v)\leqslant c(u,v)$

(2) 流量守恒：对每个节点 $u\in V\setminus\{s,t\}$ ， $\sum_{v:(v,u)\in E} f(v,u) = \sum_{v:(u,v)\in E} f(u,v)$ 即，流入量等于流出量。

1.4 净流量函数与流的值#

对任意节点 $u\in V$ ，定义净流量： $\text{net}_f(u) = \sum_{v:(u,v)\in E} f(u,v) - \sum_{v:(v,u)\in E} f(v,u)$

于是：

对 $u\in V\setminus\{s,t\}$ ： $\text{net}_f(u)=0$ （流量守恒）。
对源点： $\text{net}_f(s)=\left\lvert f\right\rvert$ 。
对汇点： $\text{net}_f(t)=-\left\lvert f\right\rvert$ 。

注：在标准建模中，通常没有边指向源点，此时第二项为 $0$ 。

Part. 2 割的定义#

设 $S\sub V$ 满足 $s\in S$ 且 $t\notin S$ 。令 $T=V\setminus S$ 。

割是指集合对 $(S,T)$ 。

割的容量定义为： $c(S,T) = \sum_{\substack{(u,v)\in E \\ u\in S,\,v\in T}} c(u,v)$

即从 $S$ 指向 $T$ 的边的容量之和。

最小割是指容量最小的割。

Part.3 最大流最小割定理#

定理：对任意流网络，最大流的值等于最小割的容量： $\max\left\lvert f\right\rvert = \min_{S: s\in S,\,t\notin S} c(S,T)$

::::info[证明]

$1\degree$ 弱对偶性（流 $\leqslant$ 割）#

引理 1：对任意可行流 $f$ 和任意 $s{-}t$ 割 $(S,T)$ ，有 $\left\lvert f\right\rvert \leqslant c(S,T)$ 。

:::info[证明]

首先，可将 $\left\lvert f\right\rvert$ 写成 $S$ 中所有节点的净流量之和： $\left\lvert f\right\rvert = \sum_{u\in S} \text{net}_f(u)$

将净流量展开：

\left\lvert f\right\rvert &= \sum_{u\in S} \left( \sum_{v:(u,v)\in E} f(u,v) - \sum_{v:(v,u)\in E} f(v,u) \right) \\ &= \sum_{u\in S}\sum_{v:(u,v)\in E} f(u,v) - \sum_{u\in S}\sum_{v:(v,u)\in E} f(v,u) \end{aligned}$$ 交换求和顺序。第一项中，$(u,v)$ 的起点 $u$ 在 $S$ 中；第二项中，$(v,u)$ 的终点 $u$ 在 $S$ 中，等价于起点 $v$ 可以属于 $S$ 或 $T$。将第二项按起点分类：

\left\lvert f\right\rvert = \sum_{u\in S,,v\in V} f(u,v) - \sum_{v\in V,,u\in S} f(v,u)