本文将不定期更新
图论建模
行列二分图
给一个二维平面，建立二分图，左部点编号为横坐标，右部点编号为纵坐标，平面上一个点即为二分图上一条边。
CF1140F Extending Set of Points
建立行列二分图，把每一个点看成一条边，则题述操作会将一个连通块变为完全二分图。使用线段树分治+并查集即可解决问题。
网络流建模
Hall 定理
对于一个二分图，设其左部点集合为 \(S\)，右部点集合为 \(T\)，边集为 \(E\)，设 \(f(V)=\{v\in T\mid\exist u\in V,(u,v)\in E\}\)（即 \(V\) 的邻域），则该二分图最大匹配为 \(|S|-\max(\max\limits_{V\subseteq S}\{|V|-|f(V)|\},0)\)。
证明：
根据最大流最小割定理，设左部点没有匹配的集合为 \(V\)，则 \(f(V)\) 均应被割掉，此时的割大小为 \(|S|-|V|+f(V)\)，对所有 \(V\) 取 \(\min\)，即可得到 \(|S|-\max(\max\limits_{V\subseteq S}\{|V|-|f(V)|\},0)\)。
最小割模型
OIFC NOI2023省队集训 三分网络
划分点集问题，想到转最小割。
把原图上点 \(u\) 拆成 \(u\) 和 \(u'\)，把原图上边 \((u_i,v_i)\) 拆成 \((u_i,v_i')\) 和 \((v_i,u_i')\)，边权均为 \(w_i\)。根据 \(u\) 和 \(u'\) 在割的哪侧可以产生 \(4\) 种状态，不少于我们需要的类数 \(3\)。
考虑最小割 \((S,T)\) 上 \(u\) 和 \(u'\) 所在集合：
- \(u\in S,u'\in T\)，令这样的点划分进 \(A\)。
- \(u\in T,u'\in S\)，令这样的点划分进 \(B\)。
- 其余情况，令这样的点划分进 \(C\)。
除 \(C-C\) 类边外，其他边都已满足要求。仔细考虑一下，\(C-C\) 类边真的不满足吗？其实也满足要求，因为如果 \(C-C\) 类边产生了 \(2w_i\) 的贡献，必然可以调整使得贡献变为 \(0\)。
连接 \((s,a,+\infty),(a',t,+\infty),(b',t,+\infty),(s,b,+\infty)\)，跑最大流即可。