|
|
|
|
给出两类点一类 B 个, 一类 R 個 B + R > N ,然后让我们选出 N 个点,使这两类中的点的最小距离最大
最小距离最大,看到这句话我们首先就要想到二分。
我们二分***然后看这个***带进去会怎么样?
但是我们又会想了我们要怎么样判断呢?
比如说下图左面有三个点,右面有三个点
他们之间的连边是 怹们之间的距离大于等于我们枚举的***。
这个时候我们跑二分图匹配吗
在仔细想一下, 我们选择 A 到 EB 到 D,找到两个最大匹配但是我們 看到 D 与 A 之间的距离并不大于枚举的数。不可行
就算我们选择了 A E,B F然而我们选择得两类的点的个数是一样的。这样有可能不符合要求因为两类中的点可以不一样。
这样我们就可以想到我们就是要求 这个图的最大团,(比如下图最大团就是:字母类中选择几个元素,数字类中选择几个元素然后两个类中选择的元素两两之间都要有一根线连着。下图就是 ABCD 和 2 3)
这个题我们要求的就是 最大团两类中选擇的元素必须要有一根线连着,说明他们之间的距离是大于枚举的数我们只要求最大团的元素有多少个就行,如果大于等于N就是说明枚舉的数小了反之就是大了。
问题又来了我们怎么求最大团呢?
这个时候我们可以反向考虑一下如果我们考虑这个图的补图会怎么样呢?
所以 补图的最大独立集 = 原图的 最大团(补图,连着的边没有了因为最大团的时候每个点都有边,现在消去了那就成了独立的点叻)
然后 最大独立集 = 所有点 - 最小点覆盖。
最小点覆盖 = 二分图匹配
所以 最终我们要求的就是 补图的二分图匹配 ,然后拿 所有点 - 补图的二分圖匹配
得到的值就是原图的最大团 与 N 进行比较,来判断区间的 l r 的变化