最大流
我选择dinic算法
总体思路就是先跑bfs分层,找出一条增广路并增广
有一个大思路,就是反悔边,流一条边不一定是最优的,所以要建一条反向边,流过该边,将它的流量减少的同时,将它的反向边流量加大,这样就相当于给了一个流回去的机会,好理解吧
就是如此,tot记得赋值为1,反向边为\(x\otimes1\)很方便处理
费用流学习
在学了最大流的基础上,学习费用流是很简单的
费用流就是把dinic的分层改为跑spfa分层,但因为最短(长)路不同于增广路,就可能会有许多条或者有负环,在dfs增广时应当判是否走过该点
好理解的,记录
实战
记录几条
- 找到流动的量,该量可以形式化为网络流的流量并带入网络中
- 源点流量为\(\infty\),因而如果要传递一个固定量,从源点到该点连边是个好选择
- 认真思考每个量的意义,要不要化为费用流,要不要把一个点分成两半处理
- 两半的目的:两半意义相连,且有时候有必要区分,如上半有流量流到下班且前面的点有流到下班的情况