学习笔记 - 最大流与最小割

网络流

对于一个网络图 \(G=(V,E)\) 的任意一个合法的流函数 \(\forall x,y\in V,f(x,y)\) 。

定律：

容量限制：\(f(x,y)\le c(x,y)\)

斜对称：\(f(x,y) = -f(y,x)\)

流量守恒：$\forall x\neq S,x\neq T, \Sigma_{(u,x)\in E}{f(u,x)}=\Sigma_{(x,v)\in E}{f(x,v)} $

可抽象理解为有一个源点和汇点，源点里有无限的流，向周围流出，最后到达汇点。

最大流

源点到汇点最大的流函数叫最大流。

当这个图中还存在一条路径可以从源点到达汇点，且路径上当前的最小容量限制大于零的时候，显然不是这个图的最大流，而这条路就叫增广路。

求法

1. 建立反向边

对一个有向图，我们建立每个有向边的反向边，之后进行递归寻找增广路。

刚开始的时候，正向边（方便表达，即原本的边）的权值即为这条边的容量限制，反向边的权值为零。并且在任何时候，我们要求正向边和反向边的权值之和为这条边的容量限制。

2. 寻找增广路

所以，我们每找出一条可以由源点到达汇点的路（即增广路），就将这条路径上所有的边都减去路径上最小的那个权值，并将这条路径的反向路径都加上这个权值。注意，这里增广路上的边不仅可以是正向边，也可以是反向边，正向边的反向即反向边，反向边的反向即正向边。

3. 统计这条增广路上的贡献

每找到一条增广路，就将这条路径改变的权值加入答案，最后当再也找不到一条增广路（即源点无法到达汇点）的时候，最大流就求出来了。

4. 回到2.，继续寻找增广路

做法理由

如果我们正常建边，不建反向边，在进行深搜递归寻找增广路的时候就会遇到问题。

我们递归的时候所选的当前节点连向的下一条边是从所有起点为当前节点的边中随机选一条（可能不是随机，其根本是根据你加边时的顺序）。这就会很容易的导致可能会有两条增广路的贡献会比当前选的这一条增广路对答案的贡献更大。

这种现象的根本原因是因为当前选的边会对答案的统计造成影响，在源点到达当前这个点的路径和当前这个点到达汇点的路径不同的情况下，会对以后寻找增广路的步骤产生影响，导致我们通过这种做法得到的路径和最大流应该的路径不同。

所以我们应该要用一种不会影响最后得到的路径的方法。这里可以分为两类主要的方法，其中一类就是严格控制路径，但是我们显然不会预先知道最大流的路径是什么。所以我们这里要使用一种可以撤销原先影响的操作。

这种操作就是加反向边，当我们当前寻找的一条增广路上有一部分（连续的）路径是经过了反向边的时候，这就意味着我们撤销了原先的操作，把原先的部分经过这条反向边的流量退了回去，让他从这条反向边的终点的那个节点换一条路径走到汇点，而不是经过这条反向边的反向边（即原来的正向边）。

应用这种原理的前提条件就是，我们的反向边代表我们以前经过这条边的流量大小，当我们经过这条反向边的时候，意味着原先从这条反向边通过了流量变小了，改换了这个点连着的其他路径，而这条原本的增广路的剩余流量代替了原先经过这条边正向边的剩余路径的流量。

我学的做法是Dinic

queue < int > q ;
bool bfs ( )
{
	memset ( dis , 0 , sizeof ( dis ) ) ;
	dis [ s ] = 1 ;
	q .push ( s ) ;
	while ( ! q .empty ( ) )
	{
		int x = q .front ( ) ; q .pop ( ) ;
		for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
		{
			int y = edge [ i ] .to ;
			if ( dis [ y ] || ! edge [ i ] .len )
				continue ;
			dis [ y ] = dis [ x ] + 1 ;
			q .push ( y ) ;
		}
	}
	return dis [ t ] ;
}

int dfs ( int x , int now )
{
	if ( x == t )
		return now ;
	int res = now ;
	for ( int i = head [ x ] ; i && res ; i = edge [ i ] .nxt )
	{
		int y = edge [ i ] .to ;
		if ( dis [ y ] != dis [ x ] + 1 || ! edge [ i ] .len )
			continue ;
		int w = dfs ( y , min ( edge [ i ] .len , res ) ) ;
		if ( ! w ) dis [ y ] = -1 ;
		edge [ i ] .len -= w ;
		edge [ i ^ 1 ] .len += w ;
		res -= w ;
	}
	return now - res ;
}


	int tmp = 0 ;
	while ( bfs ( ) )
		while ( tmp = dfs ( s , INF ) )
			ans += tmp ;

弧优化：

我们发现上面的做法，在每次bfs完成后，到达这个节点能够通过的总流量是一定的，当连接这个点的一条边的流量流满了之后，我们不管怎么算，也不会在当前这组bfs的标号中再使用这条边，或者这条边的反向边。因为bfs的标号就意味着某一条边在这次标号中只能用正向边，或者只能用反向边，否则就得等到下次标号再改变。

所以，我们可以记录之前到达这条边的最后一条边，在邻接表中直接从上次最后一次用到的边再往后跳。

queue < int > q ;
bool bfs ( )
{
	memset ( dis , 0 , sizeof ( dis ) ) ;
	dis [ s ] = 1 ;
	q .push ( s ) ;
	while ( ! q .empty ( ) )
	{
		int x = q .front ( ) ; q .pop ( ) ;
		for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
		{
			int y = edge [ i ] .to ;
			if ( dis [ y ] || ! edge [ i ] .len )
				continue ;
			dis [ y ] = dis [ x ] + 1 ;
			q .push ( y ) ;
		}
	}
	return dis [ t ] ;
}

int dfs ( int x , int now )
{
	if ( x == t )
		return now ;
	int res = now ;
	for ( int i = cur [ x ] ; i && res ; i = edge [ i ] .nxt )
	{
		int y = edge [ i ] .to ;
		cur [ x ] = edge [ i ] .nxt ;
		if ( dis [ y ] != dis [ x ] + 1 || ! edge [ i ] .len )
			continue ;
		int w = dfs ( y , min ( res , edge [ i ] .len ) ) ;
		if ( ! w ) dis [ y ] = -1 ;
		edge [ i ] .len -= w ;
		edge [ i ^ 1 ] .len += w ;
		res -= w ;
	}
	return now - res ;
}

	int tmp = 0 ;
	while ( bfs ( ) )
	{
		for ( int i = 1 ; i <= n * m * 2 + 2 ; ++ i )
			cur [ i ] = head [ i ] ;
		while ( tmp = dfs ( s , INF ) )
			ans -= tmp ;
	}

最小割

割就指去掉某些边，使得源点的流量无法留到汇点处（指一点也流不到），其中这些去掉的边的容量就是这个割的花费。

最小割就是指所有割中花费最小的一个。

有定理：最大流等于最小割

就是最大流的流量等于最小割的花费。

无需证明，因为我也不会

最小割经典例题：

1.一个图分成两部分，一半与起点相连，一半与重点相连

luoguP2046

2.对偶图

luoguP4001 , luoguP2046

3.一个物品有两类选择，两类不可同时选中

luoguP1646 , luoguP1935