关于模型
-
傻逼型
看一眼解决问题
-
拆点模型
要限制某个点的流量或者一个点在多个条件下往往需要用到，其他模型多与混合
- 限流型
限制点$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们树上路径的最小边的权值
可以用分治来搞
