回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

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

NC107617 poj3020 Antenna Placement

问题： n * m的矩阵，有一些障碍点，用12的骨牌覆盖所有非障碍点 (12骨牌可重叠，骨牌可越界，骨牌可延伸到障碍点) 问最少需要多少个。题解： • 尽量用一个骨牌覆盖两个格子，覆盖不了了再重叠使用骨牌• 用和上一个题一样的方式求一个最大匹配，那么就有（2 * 最大匹配）个点已经被覆盖了• 剩...

二分图匹配 **

2021-01-14

0 584

NC51272 棋盘覆盖

题目：给出一张n×n(n≤100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。题解：先进行黑白染色，相邻的两个黑白就是一个骨牌，又因为一个格子不能放多个骨牌，所以相当于找每个格子的搭档（搭档即为相邻的点），使得搭档的数量足够多裸的二分图最大匹配代码：

二分图匹配 ***

2021-01-14

0 779

二分图匹配(二)

@[toc] 例题： NC20483 [ZJOI2009]假期的宿舍题目描述：学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直...

二分图匹配题目集h

2021-01-13

0 688

NC107638 poj3041 Asteroids

题目描述：网格图中有若干个陨石，每次发射武器可以打掉某一行或某一列的所有陨石，求打完所有陨石的最少次数题解：首先，贪心的打星球最多的行/列有反例，如： 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 正解：我们把行和列抽象为点，把陨石抽象为边，即当（x,y）有一个陨石的...

二分图匹配匈牙利算法

2020-12-16

0 608

NC51316 Going Home

题目描述： n 个小人回到 n 间房子，要求一对一，告诉每个人的位置和每个房子的位置，问n个人移动的总距离最少是多少题解：最小权值匹配模板我们分别记录人和房，然后人与房连边并记录边权将所有边权值取相反数，然后跑一遍最优权值匹配模板详细看代码，仔细看看怎么构造图代码： #include<i...

二分图匹配最优匹配

2020-12-16

2 545

NC20483 [ZJOI2009]假期的宿舍

题目描述：学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B ...

二分图匹配匈牙利算法 **

2020-12-15

2 602