• 网络流是求网络最大流的算法，看似没什么用，实际上很多题目都可以通过建图转化为网络最大流问题

P3376 【模板】网络最大流

概念

• “网络最大流问题”本身是指从一个原点 \(s\) 往外流水，这个原点本身有无穷多水可以流，有 \(m\) 根双向管道连接 \(n\) 个节点，每个节点都有一个最大流量，指的是这根水管最大可以承载的水流量。有一个汇点 \(t\)，问从原点向汇点流水的最大流量。

反向边

• 容易想到，如果现在图上还有路可以走，即还有一条路可以让水流到\(t\)，我们将这种路称为增广路。那么将这条增广路流了一定不亏。
• 但这样并不能保证最优，那么通过什么方法来保证我流了这条路后面还有办法反悔呢？
• 这里有一种非常巧妙的方法。为每一条边建一条权值为零的反边。如果我们发现某条路不优，那么就可以流回去（毕竟流量可以随意分配）。
• 我们对于这种路并不需要特殊处理，就像dfs的回溯一样，是对最优解的自发寻找。只需要每次流过一条边时，使其反边的流量加上这次的流量（因为正边会减少这次的流量）。
  
• 假设这是初始的状态
  
• 假设经过了一次增广（就是把某条增广路走满）后的图是这样的（这里的蓝色值是反边的流量）
• 这里如果没有反向边，那么程序就已经结束了（因为找不出增广路了）。但显然这并不是最优解。因此反向边的作用就凸显出来了
  
• 在有反向边的情况下，显然还有一条绿色的增广路。这时才真正意义上找到了最优解。观察最终状态，发现中间那条路实际上是没走的。因此，反边的作用就是对可能不优的方案进行“反悔”操作。

dinic算法

• 综上，我们具体需要解决两个问题：
  1.找到是否有增广路
  2.对增广路进行修改并统计答案
• 对于是否有增广路的问题，可以直接用bfs来寻找。
• 但是，在bfs的过程中，我们还需要建立分层图，即给每个点维护其到 \(s\) 的最小边数。这里，还是以上图为例，给上图标上层数
  
• 为什么要标上层数呢？因为如果我们发现原图有增广路，那么就可以 从 \(s\) 开始dfs，依次算增广路。这里的图不是很好，如果有一个点最大流量比较大，那其就可以给很多与其相连的边分流量。如果没标层数，那这个边与其反边就可能反复互相流，造成极大的时间浪费。如果我们按照层数一层一层流，就可以保证每次都能靠近 \(t\)。同时，由于层数的限制，我们可以一次增广多条增广路。
• 但是，这里还是有些问题。相邻两个点 \(u、v\) 间的层数差并不是1，就可能造成无法增广的情况。
• 事实上，这种情况是没有影响的。由于每次增广完后都会重新bfs，重新计算层数，因此上述情况证明 \(u\) 到 \(v\) 这条路并不是到 \(t\) 的最短路，就算这条路会在最终的答案中，也会在 \(u\) 多次被增广后与 \(v\) 层数相差一，即 \(u、v\) 两个点在到 \(t\) 的同一条相对短的路径上。

当前弧优化

• 这个算是比较好理解的一条优化。在同一次dfs中，对于其枚举的前几条边，其到 \(t\) 的路径一定是被流满了的。如果再次dfs到这个点，那就不用考虑这前几个已经被流满了的点了。

几个小细节

1. 由于对于流了的每条边，我们都要对其反边加上其流量，因此这里考虑用链式前向星，点的编号从1开始，在加边的时候正反边一起相邻加，对于某边的反边，其编号就是边的编号异或1。
2. 在dfs时，如果某个点无法流到 \(t\)，即流量为0，就将其层数设为 \(inf\)，让其不再被更新（注意改层数只是对于这一次dfs而言，对下一次没有影响）
3. 注意每次bfs时将当前弧优化的数组以及层数初始化回去

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
const ll inf=1e18+10;
ll n,m,s,t,head[N],tot=1,dep[N],now[N],ans=0;
//now->当前弧优化数组 tot从1开始 
struct node
{
	ll nxt,to;
	ll val;
}e[N];

void add(ll u,ll v,ll w)
{
	e[++tot].nxt=head[u];
	head[u]=tot;
	e[tot].to=v;
	e[tot].val=w;
}

bool bfs()
{
	for(ll i=1;i<=n;i++) dep[i]=inf;//记得初始化 
	queue <ll> q;
	q.push(s);dep[s]=1;
	now[s]=head[s];                //同样得初始化 
	while(!q.empty())//广搜 
	{
		ll u=q.front();q.pop();
		for(ll i=head[u];i;i=e[i].nxt)
		{
			ll v=e[i].to;
			if(e[i].val&&dep[v]==inf)
			{
				q.push(v);
				now[v]=head[v];
				dep[v]=dep[u]+1;
				if(v==t) return 1;
			}
		}
	}
	return 0;
}

ll dfs(ll u,ll sum)
{
	if(u==t) return sum;
	ll k=0,res=0;
	for(ll i=now[u];i;i=e[i].nxt)
	{
		now[u]=i;
		ll v=e[i].to;
		if(e[i].val&&dep[v]==dep[u]+1)
		{
			k=dfs(v,min(sum,e[i].val));//尽可能流最大流量 
			if(k==0) dep[v]=inf;       //流不到汇点 
			e[i].val-=k;e[i^1].val+=k;//其反边加 
			res+=k,sum-=k;
			if(!sum) break;
		}
	}
	return res;
}

int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);add(v,u,0);//建权值为0的反向边 
	}
	while(bfs())
	{
		ans+=dfs(s,inf);//不断找增广路 
	}
	cout<<ans<<endl;
}