最小点覆盖文章列表

[luoguP3231] [HNOI2013]消毒（最小点覆盖 + 状压）

传送门 考虑贪心，控制某一维为1，另两位最大是最优的，也就是一次选一个厚度为1的面 那么对于每个点，可以有3种面是可以选到它的 然后gg 考虑二维的状态，一个平面，有些点，一次选一行或一列最优 那么每...最小点覆盖,最大匹配,二分图,状态压缩

[luoguP2774] 方格取数问题（最大点权独立集）

传送门 引入两个概念： 最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色，使得相邻两点颜色不同，之后把两个...最大流,网络流,最大独立集,最小点覆盖,最小割

网络流24题

最小割=最大流 最大权闭合图=正权边之和最小割 听说这24个题很好。 开始填坑吧。 1.飞行员配对方案问题 二分图最大匹配 传送门 （好像就是个模板呀） 2.太空飞行计划问题 最大权闭合图 传送门 3...网络流,匈牙利算法,二分图,最大流,最大权完美匹配

[POJ3041] Asteroids（最小点覆盖-匈牙利算法）

传送门 题意： 给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，最少要几次。 解析： 把每一行与每一列当做二分图两边的点。 某格子有障碍，则对应行与列连边。 选出...二分图,匈牙利算法,最小点覆盖

共1页/4条

---

香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化