[Gym 101666]E - Easter Eggs (二分 + 二分图匹配 + 找最小点覆盖（原图最大团） )

Easter Eggs

Easter is coming and the Easter Bunny decided to organise a chocolate egg hunt for the children. He will hide two types of eggs: blue milk chocolate and red dark chocolate. In the field there are some redberry and some blueberry plants where the Easter Bunny could hide the eggs. Red eggs should be hidden in a redberry plant and blue eggs in a blueberry plant. The local government has issued a permit for the event, under the condition that exactly N eggs are hidden. As they do not pay for the dental care plans of the local children, the Easter Bunny gets to decide himself how many eggs to hide of each colour. According to the yearly tradition, there is a big reward for the first child to find both a red and a blue egg. In order to make the hunt as challenging as possible, the Easter Bunny wants to maximise the minimum distance between a red and a blue egg. To keep things fair, he will hide at most one egg in each plant. Your task is to write a program to help him accomplish his goal.

Input

One line containing three integers N,B,R, the number of eggs to hide N ≤ 250, the number of blueberry plants B < N and the number of redberry plants R < N;

• B lines, each containing two integers −104 ≤ x,y ≤ 104, indicating the coordinates (x, y) of a blueberry plant;
• R lines, each containing two integers −104 ≤ x,y ≤ 104, indicating the coordinates (x, y) of a redberry plant.

The B + R plants are guaranteed to have distinct coordinates. Moreover, N is guaranteed to satisfy N ≤ B + R. Output

Output

Output a single line containing a floating point number, D, the largest minimum distance between a red and a blue egg that can be achieved. You are required to output D with absolute precision 10−6, i.e. with at least 6 decimal places.

Example

Input 1

1 2 3 4 5

3 2 2 0 0 1 0 2 0 3 0

Output 1

1	2.000000000000000

Input 2

1 2 3 4 5 6 7

4 3 3 0 0 1 2 -1 2 0 1 -1 -1 1 -1

Output 2

1	3.000000000000000

 

题意：

给出两类点，一类 B 个， 一类 R 个， B + R > N ,然后让我们选出 N 个点，使这两类中的点的最小距离最大。

 

思路：

最小距离最大，看到这句话，我们首先就要想到二分。

我们二分答案。然后看这个答案带进去会怎么样？

但是我们又会想了，我们要怎么样判断呢？

比如说下图，左面有三个点，右面有三个点。

他们之间的连边是 他们之间的距离大于等于我们枚举的答案。

这个时候我们跑二分图匹配吗？

在仔细想一下， 我们选择 A 到 E，B 到 D，找到两个最大匹配。但是我们 看到 D 与 A 之间的距离并不大于枚举的数。不可行。

就算我们选择了  A E，B F，然而我们选择得两类的点的个数是一样的。这样有可能不符合要求，因为两类中的点可以不一样。

这样我们就可以想到，我们就是要求 这个图的最大团，（比如下图，最大团就是：字母类中选择几个元素，数字类中选择几个元素，然后两个类中选择的元素两两之间都要有一根线连着。下图就是 ABCD 和 2 3）

这个题我们要求的就是 最大团，两类中选择的元素必须要有一根线连着，说明他们之间的距离是大于枚举的数。我们只要求最大团的元素有多少个就行，如果大于等于N就是说明枚举的数小了，反之就是大了。

问题又来了，我们怎么求最大团呢？

 这个时候我们可以反向考虑一下，如果我们考虑这个图的补图会怎么样呢？

所以 补图的最大独立集 = 原图的 最大团。（补图，连着的边没有了，因为最大团的时候每个点都有边，现在消去了，那就成了独立的点了）

然后 最大独立集 = 所有点 - 最小点覆盖。

最小点覆盖 = 二分图匹配。

所以 最终我们要求的就是 补图的二分图匹配 ，然后拿 所有点 - 补图的二分图匹配

得到的值就是原图的最大团， 与 N 进行比较，来判断区间的 l  r  的变化。

至此，此题结束。

#include <bits/stdc++.h>
using namespace std;
#define mem(x,v) memset(x,v,sizeof(x))
struct node
{
	double x,y;
}Red[300],Blue[300];
int N,B,R;
int match[300]; //匹配
double len[300][300]; //预处理
bool vis[300];
double mid;
bool dfs(int u){
	for (int i = 0; i < R; i++ ){
		if (len[u][i] < mid && vis[i] == 0){
			vis[i] = 1;
			if (match[i] == -1 || dfs(match[i])){
				match[i] = u;
				return 1;
			}
		}
	}
		return 0;
}
int big_matching(){
	int ans = 0; //这个是最小点覆盖
	mem(match,-1);
	for (int i = 0; i < B; i++){
		mem(vis,0);
		if (dfs(i)) ans++;
	}
    return B + R - ans; //这个才是我们要二分出来的东西。
}

int main(){
	scanf("%d%d%d",&N,&B,&R);
	for (int i = 0; i < B; i++)
		scanf("%lf%lf",&Blue[i].x, &Blue[i].y);
	for (int i = 0; i < R; i++)
		scanf("%lf%lf",&Red[i].x, &Red[i].y);
	for (int i = 0; i < B; i++)
		for (int j = 0; j < R; j++)
			len[i][j] = sqrt((Blue[i].x - Red[j].x)*(Blue[i].x - Red[j].x) + (Blue[i].y - Red[j].y)*(Blue[i].y - Red[j].y));
	double l = 0, r = 5e4;
	int Ans;
	for (int i = 0; i < 100; i++){
		mid = (l + r) / 2;
		Ans = big_matching();
		if (Ans >= N) l = mid; else r = mid;
	}	

	printf("%.9lf\n",l);



	return 0;
}