YZHT Ep.1: 最大流+图论优质好题
欢迎来到YZHT系列,这个系列我将分享我遇到的OI好题。
第一题
笔者最近正在学习数学图论,但是在OI中正巧碰到了这样一道从来没见过的最大流题。虽然难度不大,但是思路比较新:
Problem B of 2023-2024 ICPC Southwestern European Regional Contest (SWERC 2023)
顺便说一下这一场欧洲的题可能机子不太行,特别喜欢把时间和内存锁的很紧,A题卡了我一小时常熟,笔者表示强烈谴责!
这道题一看网络流,但是笔者第一眼思考了很多传统的建图方式都没有想出来。但是,它本质上其实是一个二分图的最小顶点覆盖,而二分图中有Konig Theorem,就可以把他转化为最大匹配问题,而最大匹配问题又可以转化成最大流,做完了!
所以现在最大流不仅要考虑建图、最小割转化、最大匹配转化,还要尝试一下最小顶点覆盖转化。话是这么说,做题切忌陷入形式当中。
版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/1390
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。
THE END
二维码
文章目录
关闭
共有 0 条评论