ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共2篇）

bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群最小点覆盖

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1741 思路消除所有的小行星每个点(x,y)只有选择x或者y才能被覆盖二分图最小点覆盖=最大流首先，最小顶点覆盖一定>=最大匹配，因为假设最大匹配为n，那么我们就得到...

网络流最小点覆盖

2019-02-18

0 524

bzoj 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场最小点覆盖

链接 1735: [Usaco2005 jan]Muddy Fields 泥泞的牧场思路这就是个上一篇的稍微麻烦版(是变脸版，其实没麻烦) 用边长为1的模板覆盖地图上的没有长草的土地，不能覆盖草地每个点(x,y)只有选择x或者y才能被覆盖还是最小点覆盖，证明在上一篇横边和竖边得遍历一...

网络流最小点覆盖

2019-02-18

0 631