louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共2篇）

题解 | 算法竞赛进阶指南 Muddy Fields

思路因为木板可以重叠,所以如果放置木板,木板两端肯定都顶到底(障碍或者边界)是最优的.这样就可以预处理出一些横向与纵向的联通块(宽度都为1).因为每一个方格必须被覆盖,所以该方格隶属的横向联通块与纵向联通块至少有一个被木板覆盖.这样就可以构建二分图,横向联通块为左部图,纵向联通块为右部图,每一个方...

二分图最小点覆盖

2019-08-24

0 597

题解 | 算法竞赛进阶指南 Machine Schedule

思路很裸的二分图最小点覆盖题.首先,因为最开始都处于0模式,那么或的边都可以删去.然后因为最优情况下每种模式最多只转换一次,可以把转换过这种模式看作选择这种模式所代表的的点,而可以看作一条边.的模式是左部图,的模式是右部图.很明显,题目转换成这样一个问题:选择最少的点,使所有边都能覆盖到.这就是经...

二分图最大匹配二分图最小点覆盖

2019-08-24

0 495