网络流整理

关于模型

• 傻逼型

看一眼解决问题

• 拆点模型

要限制某个点的流量或者一个点在多个条件下往往需要用到，其他模型多与混合

• 限流型

限制点$i$只能选/经过$k$次

$(i,i+n,k)$

• 满足多个条件型

满足条件$a$流量为$A$，满足条件$b$流量为$B$，……

$(S,i,A),(S,i+n,B),……$

• 取数模型

常见的费用流模型

一个位置最多能取$k$次数$w$，最多经过$l$次，用到了拆点

$(i,i+n,k,w),(i,i+n,l,0)$

• 黑白染色模型

常用于最小割棋盘类

对于格子$(x,y)$，选择ta之后就不能选择格子$(x-1,y),(x+1,y),(x,y-1),(x,y+1)$，奇数点染成黑色，偶数点染成白色，$S$连黑色格子，白色格子连$T$跑最小割

解决某些适用于所有/指定格子且互不影响的条件

• 染色模型

黑白染色的拓展，有多个限制分类讨论，颜色之间再相连

• 二分流量模型

常用于一些满足某种条件的最大/小值问题

二分一个流量，使得所有边的流量对二分值取$max/min$，看是否满足总流量/费用条件（是否合法）

• 士兵占领模型

解决行列问题，当满足第$i$行至少放置了$L_i$个士兵, 第$j$列至少放置了$C_j$个士兵，整个棋盘就全部被占领，问最少需要士兵数

$(S,i,L_i),(i,j,1),(j,T,C_j)$

• 泡泡堂模型

士兵占领模型的变种，可以占领两个阻碍之间的区域

把对于行的所有区域和对于列的所有区域单独处理，然后连接

$(S,X_{l_1,r_1},1),(X_{l_1,r_1},Y_{l_2,r_2},1),(Y_{l_2,r_2},T,1)$

• 消毒模型

士兵占领模型的变种，每次可以花费$1$占领一行或一列，占领的区域可以有重叠，问占领给定区域最小花费数

相当于一个最小点覆盖

$(S,i,1),(i,j,1),(j,T,1)$

• 电驴模型

每个点只能按某种顺序到达一次，点$i$可以通过连边到达点$j$或者某种通用方式到达点$j$，通用方式不受出发点影响

$S$与$i$连两条边，一条表示通用方式到达，一种表示$i$为出发点；同时每个点都与$T$相连，表示总流量为$n$，也是拆点的应用

$(S,i,1,0),(S,i+n,1,w_i),(i,j+n,1,c_{i,j}),(i,T,1,0)$

• 餐巾模型

类似于电驴模型，最大的特点是流量不固定（有多余流量）和上一个点可以影响下一个点

单独考虑每一天，每一天可以从$S$新进流量（买餐巾），也可以从前面天进流量（洗好的），所以就相当于电驴模型的操作了

因为流量可以从上一天传递下来，所以上一天与下一天连边

• 交换棋子模型

可以构成某条路径，路径中间是一个流量，头尾单独讨论

对于路径$(u,v)$，将一个点拆成$3$个点，$l_i\rightarrow i \rightarrow r_i,S\rightarrow u_i,v_i\rightarrow T$，中间点$l_i\rightarrow i,i\rightarrow r_i$流量都为$\frac {w_i}{2}$

• 切糕模型

相邻点之间有距离限制，需要转换成单向限制

关于其他

• 最小顶点覆盖

选择点$i$就相当于覆盖与点$i$相连的边，求最少选多少个点能把整个图覆盖

等于求二分图的最大匹配，跑最大流即可

• 最大独立集

选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集，包含顶点数最多的独立集称为最大独立集

发现把最小顶点覆盖求出的点去掉，整个二分图是不连通的

所以$最大独立集=n-最小顶点覆盖$

• 最小路径覆盖（不相交）

选择不能相交的路径，求最少选多少条路径覆盖所有边

拆点建新图，则$最小路径覆盖=n-新图的最大匹配$

对于有向边$(u,v)$，新图中对应建$(u,v+n)$，每匹配一对点，相当于选一条边将ta们合并起来

• 最小路径覆盖（可相交）

选择可以相交的路径，求最少选多少条路径覆盖所有边

用$Floyd$（传递闭包）求出每两点之间的连通关系，对于连通的两个点$(u,v)$（原图中不一定直接相连），相当于ta们之间存在一条有向边$(u,v)$（原图中不一定存在），然后就是不相交的做法了

• 最长反链

反链指一个点集中的点两两不到达，最长反链指最大的这样的点集

有定理为：$最长反链=最小路径覆盖（可相交）$

• 最小割树

对于一个无向图，每次从一个集合里选择两个点$(u,v)$，求出$(u,v)$之间的最小割$k$，然后在新图里建连边$(u,v,k)$，重复上面过程

最后新图里面必定是棵树，且某两个节点之间的最小割为ta们树上路径的最小边的权值

可以用分治来搞

关于更详细的文章

$Asia$

---

• Previous
  [LUOGU2418]yyy loves OI IV
• Next
  [LUOGU3401]洛谷树