关于“最小右部覆盖问题”
  • 板块学术版
  • 楼主HYLW
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/20 17:26
  • 上次更新2024/11/20 19:44:31
查看原帖
关于“最小右部覆盖问题”
663949
HYLW楼主2024/11/20 17:26

主要是遇到过很多次这种问题了,但是总感觉捉不住头脑。

形式化地,对于一张二分图,保证有左部点的最大匹配(一定存在一种选边方案使得左部点全部存在相连边选上)。现选择一部分左部点及其边,问使得右部点全部存在相连边选上的左部点最小选择数量。
额,我语文挺 的,简而言之,选择最少的左部点,使得右部点全部都存在相连左部点被选上。

以上问题均为自定义。

然后,对于一些特殊性质的问题,显然是有做法的,例如今年CSP的T2、经典的引水入城的区间性质带来了不同的做法。

蒟蒻实力过弱,假若问题过于离谱,大佬轻喷。doge

2024/11/20 17:26
加载中...