网络流建模总结
开新坑了, 大概是天坑, 填不完的那种.
因为是给自己这种萌新写的, 所以尽量写清.
网络流这种东西间模型见得多是真的很有好处的, 不然考场硬想一个建图方法是真的很难.
要是我什么时候能自己编出来一个建图就牛逼大了hhh.
最大权闭合子图求法
对于点权为正的点, 从源点向该点连边权为该点点权的有向边.
对于点权为负的点, 从该点向汇点连边权为该点点权的绝对值的有向边.
点之间按照原图连边权为 $\infty$ 的有向边.
最终答案为 $\sum{\text{正点权}}-\text{最小割}$ .
证明参考 最大权闭合子图
集合划分
多往 最大权闭合子图 , 最小割的方向思考, 思路和建图大致相似, 先将所有利润加起来, 再减去最小代价, 即为最大利润.
四倍经验.
最小割
多数是期望什么东西最小, 这样的话考虑按贡献建图, 割一条边相当于选这个贡献, 中间可以通过加 $\infty$ 的边来调控.
一个决策影响多个限制条件
网络流的流量是一对一的, 也就是一点流量不能再某一个点 “分” 成很多流量.
这种时候一般考虑换种建图方式, 找到合适的建图方案, 不能纯粹生搬硬套模型.
路径覆盖
可重复的路径覆盖, 即下限为 $1$ , 上限为 $\infty$ 的网络流. 路径有边权同理 $(\text{即最小费用可行流})$.
有源汇转无源汇
连一条 $(t,s,\infty)$ 的边即可.
有上下界的网络流
费用流
在求一个东西最小还同时有一些限制时, 最小割不一定能找到一个很好的建图起到限制的作用, 这个时候可以选择费用流, 费用最小, 流量来做限制.