集合划分模型
求解形如
$$ \min_{x_1,x_2,\cdots,x_n}\sum_{(u,v)\in E}c_{u,v}x_u\overline{x_v}+\sum_{i}a_ix_i+b_i\overline{x_i} $$的一类的问题。
其中 $x_i\in{0,1}$，$\overline{x_i}$ 代表给 $x_i$ 取反。
实际意义为，将一些物品归于两个集合 $A,B$ 中，分别有对应代价 $a,b$，另外若 $x\in{A},y\in{B}$ 则会额外产生 $c_{x,y}$ 的代价。
处理两部集合之间的代价，可以考虑最小割，若将一组$(S,T)$割赋予实际意义，与 $S$ 连通的物品归于 $A$，与 $T$ 连通的物品归于 $B$，那么割的费用相当于选择的代价。于是可以得到建图方案。
-
$S\to i$，若这条边被割，那么 $i$ 与 $T$ 连通，则边权为 $b_i$。
-
$i\to T$，若这条边被割，那么 $i$ 与 $S$ 连通，则边权为 $a_i$。
-
$u\to v$，若这条边被割，则 $u$ 和 $v$ 一定不连通，为满足图的方向，可以令 $u$ 与 $S$ 连通，$v$ 与 $T$ 连通，则边权为 $c_{u,v}$
其中，若需要保证 $u$ 与 $S$ 连通时，$v$ 不能与 $T$ 连通，可以令 $c_{u,v}=+\infty$，强制本边不被割断。
一个简单的应用是 P8215 【THUPC2022 初赛】 分组作业，对于此题，可以对每个人是否愿意，每组是否合作建点，题中的所有代价都可以表示为以上形式。
这类方法可以解决一类成就-条件问题。比如给定一些成就，每种成就需要满足一定的条件才能达成，求最大的贡献减代价。可以先将所有的贡献都加入到答案，问题变为若成就不满足则会产生代价。我们可以对所有的成就和条件都建一个点，选择两种集合，分别对应其是否被满足。这样就规约到了集合划分模型。一个例题是 【ABC326G】 Unlock Achievement。
