简介
网络流算法在于把抽象的题目转换为图上水流问题，通常在省选及以上难度范围出现，最初由似贪心问题引出
通常在数据较小，看似可贪心但实则需要不断后悔调整的题目中可应用到
飞行员配对方案问题
发现飞行员类型仅两种，且每个飞行员至多参加一个队伍，显然这是个二分图
按类型染色，按匹配连边，跑匈牙利就能过
负载平衡问题
求出平均数(sum)，(a_i>sum)的这部分显然变化的只有(sum-a_i)，而(a_i<sum)同理
而这两部分的缺口或者增量是互补的
考虑分类分别与源点汇点相连流量为(|sum-a_i|)，相邻点连边，流量(inf)费用(1)
汽车加油行驶问题
(K)较小，考虑拆点表示状态，(pos_{i,j,k})为位于坐标((i,j))是油量还剩(k)
考虑转移：
-
有加油站的位置必须加油，：(pos_{i,j,k}(kin [0,K-1]))向(pos_{i,j,K})连容量为(1)费用为(A)的边
没油是必须加油：(pos_{i,j,0})向(pos_{i,j,K})连容量为(1)费用为(A_C)的边 -
有加油站的位置仅有(pos_{i,j,K})能向其他位置移动(保证必须加油)
其他位置(pos_{i,j,k})向(pos_{i',j',k-1})连容量为(1)的边，费用判断相对位置考虑费用为(0)或为(B)
圆桌问题
两种类型，且收支平衡，源点向单位连容量为人数的边，圆桌向汇点连容量为座位数的边
每个单位向每个圆桌连容量为(1)的边(每个单位至多一人坐在一个圆桌)
太空飞行计划问题
最大权闭合子图(总结写好了再放上来)
(ans=正权和-最小割)，正权属于仪器，最小割相当于把容量流完了，则还有源点还能到的仪器为选择的仪器
深海机器人问题
一条边的意义：第一次经过贪心地选价值，之后都不增加贡献了
则两点之间连两条边：容量为(1)费用为(val_{i,j})；流容量为(inf)费用为(0)
机器人始点源点向其连容量为人数费用为(0)的边；机器人终点其向汇点连容量为人数费用为(0)的边
餐巾计划问题
拆点：(x()早上())，(x'()晚上())
收支配合通过脏纸巾表示出来，为保证每天用量：(i xrightarrow{r_i, 0} T)
晚上收到脏纸巾：(S xrightarrow{r_i, 0} i')
购买新纸巾：(S xrightarrow{infty, p} i')
洗纸巾：(i xrightarrow{infty, f} i+m',i xrightarrow{infty, s} i+n')
新旧纸巾的延续：(i xrightarrow{infty, 0} i+1',i' xrightarrow{infty, f} i+1')
数字梯形问题
规则一：
-
点不相交：拆点(x_{i,j}xrightarrow{1, val_{i,j}}y_{i,j})
-
边不相交：(y_{i,j}xrightarrow{1, 0}x_{i+1,j},y_{i,j}xrightarrow{1, 0}x_{i+1,j+1})
源点向第一行(m)个位置连容量为(1)费用为(0)的边，汇点同理
规则二：
- 点可以相交：拆点(x_{i,j}xrightarrow{infty, val_{i,j}}y_{i,j})
最后一行与汇点的边容量为(infty)
规则三：
- 边可以相交：(y_{i,j}xrightarrow{infty, 0}x_{i+1,j},y_{i,j}xrightarrow{infty, 0}x_{i+1,j+1})
[CTSC1999]家园
发现每辆车下一站的位置和时间相关，所以按时间分层
((t,i))表示时刻(t)在(i)点，枚举车i，则((t,v_{i,t~mod~c_i})xrightarrow{h_i} (t+1,v_{i,t+1~mod~c_i}))