【算法笔记】再看网络流

最近几天,重新来看网络流的相关题目,发现之前看的基本上都忘了 QAQ
看了一个上午,有以下收获
1.最大流的正确性依赖于每一条s-t流对应了一种实际方案
2.网络流也可以作为二分的可行解判定方式
3.网络流只能在0/1之中做选择,对于1/2、2/3之类的,可以考虑降到0/1之后算贡献
4.对于割边,可以在残余网络中DFS搞一搞,一端可到源点,一端可到汇点即为割边

另外,提供一点网络流24题的相关资源:
1.完整题解:http://www.snowyjone.me/2015/07/lp-and-flow-a/
2.精选题解:https://blog.sengxian.com/solutions/networkflow-24-all
3.大神题解:https://www.byvoid.com/blog/lpf24-solution
4.OJ传送门:http://cojs.tk/cogs/page/page.php?aid=3

Leave a Reply

Your email address will not be published. Required fields are marked *