杂·网络流

· · 个人记录

P4249

对于最小化平方和问题，有一个经典差分建图：从每个点建立流量 1，费用 k 的边，前缀和就是平方。

P3749

模型：最大权闭合子图，即给定一些点，选择一个点必须选择其他一些点，最大化点权和。

建模是将点权非负的与原点连边，流量点权；点权负的与汇点连边，流量点权相反数；依赖关系直接连边，流量 inf。最终答案就是非负点权和减去最小割。

最小割建模（切糕模型）