Category Archives: Dancing_Link

hdu 5046 Airport(跳舞链,重复覆盖)

题意:n个城市,准备在n个城市中选k个建立机场,求di的最小值。di = max{ 最近的机场的距离 | 1 …

hdu 4979A simple math problem(跳舞链,重复覆盖)

题意:一个彩票由n个数组成,每次买一个张彩票可以选择其中的m个数,但是这些数字中只有r个数字是中奖数字,如果买 …

poj 3074 Sudoku (跳舞链,精确覆盖解数独)

题目就是要求解数独,那么我个人理解解释下做法。 我们知道精确覆盖的原理: 对应的列消掉,这个解的行选中,对于这 …

FZU 1686 神龙的难题(跳舞链)

题意:给出一个矩阵n*m,1表示有怪,0表示没怪,每次可以攻击一个范围的矩阵那么这个矩阵中对应的怪就是死掉,攻 …

hdu 2295 Radar(跳舞链,重复覆盖)

题意:n个城市,m个雷达可覆盖点,只能选择k个位置设置雷达,要求尽量使得雷达覆盖的半径R小,求最小的R。 这题 …

zoj 3209 Treasure Map(跳舞链,精确覆盖)

题意:给出n*m的矩形,然后给出p个块,快的坐标是已知的,问最少多少块拼起来恰好是n*m的矩形。当然不能有重叠 …

hust 1017 Exact cover(跳舞链,精确覆盖)

一道模板题,精确覆盖。 Dancing Link 可以解决一类精确覆盖问题,有些时候需要将题目抽闲成精确覆盖的 …