主要是遇到过很多次这种问题了,但是总感觉捉不住头脑。
形式化地,对于一张二分图,保证有左部点的最大匹配(一定存在一种选边方案使得左部点全部存在相连边选上)。现选择一部分左部点及其边,问使得右部点全部存在相连边选上的左部点最小选择数量。
额,我语文挺 好 的,简而言之,选择最少的左部点,使得右部点全部都存在相连左部点被选上。
以上问题均为自定义。
然后,对于一些特殊性质的问题,显然是有做法的,例如今年CSP的T2、经典的引水入城的区间性质带来了不同的做法。
蒟蒻实力过弱,假若问题过于离谱,大佬轻喷。doge