基础网络流模板

1.定义及应用场景

网络流是一种特殊的图论模型，它是一张$n$点$m$边有向图，满足以下条件:

<1>存在一对源汇点$s,t$

<2>对于每条边属于总边集$<u,v>\in E$存在一个特殊的值"容量$w$"

<3>对于每个点，它可以存储无限多的流量，但是对于每条边，它能通过的最大流量为它的容量$w$

对于网络流的模型，我们可以解决最大流与最小割的问题，同时可以将一些其它的数学或图论模型抽象变化为网络流解决

---

2.Dinic算法最大流思路与实现

因为铸币主包只学了$Dinic$且这个算法的时间复杂度大多数时候可以接受，所以就懒得写其他更复杂的方法了

首先引入一个定义"残量网络"，为目前所有边的容量与流量之差构成新边容量的网络(为零的话就是没有这条边了)

而在这个残量网络上再次寻找从$s$到$t$的路径，叫做这个残量网络的一个增广路(不一定是一条路径，也可以是多条路径的并)

不难想到，我们的最大流量可以变为多次增广路求和，于是我们现在的目标变为了寻找增广路和新残量网络的构建

对于目前的一张网络$G$，我们考虑在上面去跑一遍$DFS$，对于一个增广路$p$，我们记录它的最小流量为$v$

所以我们这个时候把每条边加上$v$流量，反向边退掉$v$流量就可以完成一条增广路的寻找与新残量网络的构建

说一下"退流"，它的作用是在贪心选择到错误的边时可以通过退流走回去，相当于没选择这条边完成类似"反悔"的操作

所以我们就可以解决网络流问题，这就是复杂度为$O(nm^2)$的$Edmonds–Karp$算法，但还是太劣了

考虑优化这个算法，在每次寻找增广路之前先进行分层，即按照从$s$到$t$的经过的深度分层，并保证每次寻找增广路时只会从上层走到下层

此时我们从这个残量网络中找出来的最大流量的增广路叫做该网络的阻塞流

所以我们的处理变成了先$BFS$分层在$DFS$找增广路然后合并知道无法分层或找不到增广路为止

为了让复杂度更优，我们还要使用当前弧优化，就是将下次的枚举边的初始设置为最后一次访问的边(具体可以看代码)

恭喜你学会了复杂度最劣$O(n^2m)$的$Dinic$算法，且这个算法平常情况下除非特意卡复杂度都是$O(n^2m^{\frac{2}{3}})$左右的

附上模板最大流的代码

#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=1e2+10, M=5e3+10;
const ll inf=1e18;

int head[N], ver[M<<1], nxt[M<<1], now[N], CNT=1;
ll edge[M<<1];
void add( int u,int v,int w )
{ ver[++CNT]=v, edge[CNT]=w, nxt[CNT]=head[u], head[u]=CNT; } 

int n, m, s, t;
int d[N];

inline void intt()
{
	for( int i=1;i<=n;i++ ) d[i]=0;
}

inline bool bfs()
{
	intt();
	queue< int > q;
	q.push( s ), d[s]=1;
	now[s]=head[s];
	while( !q.empty() )
	{
		auto x=q.front();
		q.pop();
		for( int i=head[x];i;i=nxt[i] ) if( edge[i] && !d[ver[i]] )
		{
			d[ver[i]]=d[x]+1;
			now[ver[i]]=head[ver[i]];
			if( ver[i] == t ) QAQ true;
			q.push( ver[i] );
		}
	}
	
	QAQ false;
}

inline ll dinic( int x,ll flow )
{
	if( x == t ) return flow;
	ll rest=flow;
	for( int i=now[x];i && rest;i=nxt[i] )
	{
		now[x]=i;
		if( edge[i] && d[ver[i]] == d[x]+1 )
		{
			ll sonflow=dinic( ver[i],min( rest,edge[i] ) );
			if( !sonflow ) d[ver[i]]=0;
			edge[i]-=sonflow;
			edge[i^1]+=sonflow;
			rest-=sonflow;
		}
	}
	QAQ flow-=rest;
}

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	cin>>n>>m>>s>>t;
	for( int i=1, u, v, c;i<=m;i++ )
	{
		cin>>u>>v>>c;
		add( u,v,c ), add( v,u,0 );
	}
	ll maxflow=0, flow;
	while( bfs() ) while( flow=dinic( s,inf ) ) maxflow+=flow;
	cout<<maxflow;
	QWQ	 
}