最小割模型

一个关系E,

Ei = { x, y, cost } 表示条件Ax 和 By 同时不满足时的代价为cost

CAx 表示条件Ax 满足时的代价

CBx 表示条件Bx满足时的代价

则要使总代价最小，即可构造网络

S - > Ai    容量为CAi

当Ai和Bj的关系属于E时， Ai -> Bj    容量为Ai和Bj关系的cost

Bj -> T   容量为CBj

则求这个网络的最小割即是最小代价

如NOI 06 profit:

条件Ai表示放弃某项工作Ai S->Ai的容量即为放弃时丢失的获利

条件Bj表示需要零件Bj  Bj->T的容量即为零件Bj的花费

Ai->Bj的容量为      不满足 Ai且 不满足Bj的损失

在本题中，不满足Ai 且 不满足Bj   即 选定了某项工作但是没有它必须的某个零件

根据题意这种情况非法，所以我们可以设定容量为 inf