集合划分模型
求解形如
$$
\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$ 一定不连通，为满足图的方向，可以令
学习笔记
· 2023-12-04
· 396 人浏览
yrq
