关于 网络流 的一些认识

最大流建议学Dinic,费用流建议学SPFA,其他的学了用不到.

建议省选前学会。

网络流和贪心有某种神奇的联系。

网络流本身就是一种神奇的东西。

当题目限制性强,数据范围小的时候,就可以考虑网络流。

虽然有的时候计算时间复杂度是跑不过去的,但是网络流通常情况下时间复杂度是跑不满的,而且有很多优化,并且有很多模型建出来的图不卡网络流,所以只要不是很离谱,就可以用。

建模

终究还是要建模的,跑不掉的

经常见的有 最小割,最大权闭合子图,最小路径覆盖等 。

说多了也没用,最重要的还是做题...

网络流24题建议挑着刷,重点还是学习建模

听说近几年的网络流题神仙得很,只会网络流24题的建模是不够的。

所以建议也多看看新题(同样也适用于其他算法)

最大流

写Dinic不要写错

费用流

写SPFA不要写错

有上下界网络流

通常会在一些有选择要求的题目中出现。

其实只是改变了一下建图方式,Dinic和SPFA跟板子没有区别。

原文地址:https://www.cnblogs.com/wljss/p/13154573.html