记录一下最近新学的一些网络流的 \(\text{tricks}\) 。
上下界可行流
指需要每条边的流量在 \([L_i,R_i]\) 之间，问是否存在可行解。
无源汇
转换建图：
对于原图中一条边 \((x,y,L,R)\) ，在新图中新建三条边 \((S',y,L)\) ，\((x,T',L)\) ，\((x,y,R-L)\) 。前两条边的目的是保证下界，指除了可以随意的 \(R-L\) 这一部分，\(x\) 必须流出 \(L\) ，\(y\) 必须流入 \(L\) 。判断可行即看前两条边是否被流满即可（前两条边就是保证限制），构造方案看第三条边流量为多少。
有源汇
与前者区别是，源点和汇点可以流量不守恒，但是将其视为一个点的话也要守恒。因此在新图上连边 \((T,S,inf)\) 即可，这样就满足流量守恒了。
原图中源点汇点间最大/最小流
跑完限制之后，在参量网络上由 \(S\rightarrow T\) 或者 \(T \rightarrow S\) 进行补流或者退流即可。
最小费用可行流
建图同理，加上费用即可，只将费用放在前两条边中的一条即可。
一个建图的优化
考虑每个点会向新图中的源点/汇点连很多条边，考虑将其缩为一条。缩边之后的容量为其原先容量总和，费用的话直接在外面加上就行，再将其费用设为 \(0\) 。因为如果存在可行流，这样的边必然流满。
建模
建模颇难
可行流的建模通常用于一类，并不单纯要求最大匹配，可以满足某些边必须要选/必须要选多少等一些以限制。
比如 ABC287G - Tatami 这题，要求 \(2\) 的边必须要被流，\(0\) 的边任意，单纯的最大流并不方便满足，而上下界可行流却能够很好的实现。
区间选择模型
概述
给定一个序列，有一些区间，你可以选择每个区间若干次，需要满足的限制是每个点被选择的区间覆盖恰好 \([L_i,R_i]\) 。
解法
先拉一条 \(1-n\) 的链，连边 \((i,i+1)\) ，区间 \([L,R]\) 连边 \((L,R+1)\) ，这样的意义是“抢”走了区间 \([L,R]\) 每一个点流过的一点流量。
再来考虑满足每个点的限制，假设最大流为 \(X\) ，每个点流过的流量为 \(f_i\) ，则 \(X-f_i\) 就是 \(i\) 点被覆盖的次数，因此需要满足 \(f_i\in[X-R_i,X-L_i]\) ，在区间选择模型中，最大流可以 直接钦定 ，我们取 \(X=R_i\) ，则 \((i,i+1)\) 这条边的容量就是 \(R_i-L_i\) 。
建模
模型容易，找区间太难。如何将题目转化成这个模型需要经验的积累。
P6967 [NEERC2016]Delight for a Cat
先钦定都选择睡觉，选择将一个点 \(i\) 改为吃饭，影响的是右端点在 \([i,i+k-1]\) 中的区间。考虑将区间的限制保存在右端点上，选择更改点就是选择区间覆盖，然后套用模板即可。
一些点/区间限制与次数相关可以考虑这个模型。
标签：可行,yb,扩展,网络,流量,建模,选择,即可,区间 From： https://www.cnblogs.com/oscaryangzj/p/17149518.html