YZHT Ep.1 最大流+图论优质好题

欢迎来到YZHT系列,这个系列我将分享我遇到的OI好题。

第一题

笔者最近正在学习数学图论,但是在OI中正巧碰到了这样一道从来没见过的最大流题。虽然难度不大,但是思路比较新:

Problem B of 2023-2024 ICPC Southwestern European Regional Contest (SWERC 2023)

顺便说一下这一场欧洲的题可能机子不太行,特别喜欢把时间和内存锁的很紧,A题卡了我一小时常熟,笔者表示强烈谴责!

这道题一看网络流,但是笔者第一眼思考了很多传统的建图方式都没有想出来。但是,它本质上其实是一个二分图的最小顶点覆盖,而二分图中有Konig Theorem,就可以把他转化为最大匹配问题,而最大匹配问题又可以转化成最大流,做完了!

所以现在最大流不仅要考虑建图、最小割转化、最大匹配转化,还要尝试一下最小顶点覆盖转化。话是这么说,做题切忌陷入形式当中。