图论系列知识和网络流(粗糙的笔记)

网络流。定义,流量守恒,流量限制

最简单的问题:最大流,求从源点流到汇点的最大速率。如何求:Ford-Fulkerson

最小割最大流定理

最大权闭合子图,一个有向图,如果选了一个点就必须选联向这个点的点,让权值最大。

先把答案设为所有正权值,然后从源点到所有正权边连一条权值的边,从负权点到汇点连一条权值为权绝对值的边,其他边按照题意连接。跑最大流最小割,答案减去最小割即可。如果有环则先跑强连通分量缩点。

二分图最小点权覆盖要求选出一些点覆盖所有的边,求最小点权是多少。直接把两侧的点到源汇的边权改成点权值,跑最大流最小割。

经典的费用流模型:有N个元素a_i,权值可正可负,连续M个元素中最多选K个,使得总权值最大。

转换题目,考虑选K次,每次选的两个元素间距离最小M。建图,每个点i向其后方M个点后面连一条流量1,费用为a_i的边,代表选了这个点;同时向它后面一个点连一条流量inf,费用0的边,代表不选。源向第一个点连一条流量K,费用0的边,最后一个点向汇连一条流量inf,费用0的边。跑最大费用流,费用即是答案。

bzoj3438 小M的作物,最小割(有一堆东西放到两边,都有一些收益/损失)

我们先把所有收益加到答案里,然后尝试最小割。不考虑组合收益则直接ST之间建i点,连a[i]->S, b[i]->T。现在考虑组合收益,新建一个点,如果A的组合则连S,B则连T,边权为组合收益,再向组合中的点连inf边,即可保证不种在A时可以保证舍掉组合收益。跑最小割减掉。

上下界网络流:每条边除了一个上界,还有一个下界,在这样的图上可以求环流/源汇点最小/最大/费用最小/最大可行流之类的

bzoj2502 清理雪道

发表评论

电子邮件地址不会被公开。 必填项已用*标注