Easter Eggs

题目描述：

有a和红色栖息地，b个蓝色栖息地，你需要埋n个彩蛋，可以选择放在红色栖息地，也可以选择放在蓝色栖息地，输出放彩蛋的不同颜色栖息地的最小距离的最大值

思路：

求最小距离的最大值，显然是二分答案

但是怎么check?

两种颜色，可以考虑二分图，但是二分图求什么？

最先思考的应该是给每两个距离大于等于mid的点连边，跑二分图匹配，但是这样真的对吗？显然不对，因为你不能保证所有的不同颜色的之间的距离都大于等于mid

我们考虑一下最大独立集

一个图的最大独立集指的是选出来的尽可能多的点，两两之间没有边连接

所以我们可以考虑建反图，也就是给所有的不同颜色的点之间距离小于mid的点之间连边，再求最大独立集的大小即可

如果最大独立集的大小大于等于n，则满足要求

而 最大独立集 = 点的数量 – 最小点覆盖

最小点覆盖 = 二分图匹配

所以我们check的时候，建个反图，跑二分图匹配，用总的点数a+b – 最大匹配数 来和n比较

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define y1 y114514
typedef long long ll;
typedef pair <int,int> pii;
#define eps 1e-9
#define MAX 500 + 50
int n, a, b;
struct ran{
    double x, y;
}ar[MAX], br[MAX];

double dis[MAX][MAX];
bool G[MAX][MAX];
bool vis[MAX];
int link[MAX];

bool dfs(int u){
    for(int v = 1; v <= b; ++v){
        if(!vis[v] && G[u][v]){
            vis[v] = 1;
            if(!link[v] || dfs(link[v])){
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

bool judge(double mid){
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            G[i][j] = (dis[i][j] < mid);
        }
    }
    int ans = 0;
    mem(link, 0);
    for(int i = 1; i <= a; ++i){
        mem(vis, 0);
        if(dfs(i))++ans;
    }
    return a + b >= n + ans;
}

double getdis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void work(){
    cin >> n >> a >> b;
    for(int i = 1; i <= a; ++i)cin >> ar[i].x >> ar[i].y;
    for(int i = 1; i <= b; ++i)cin >> br[i].x >> br[i].y;
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            dis[i][j] = getdis(ar[i].x, ar[i].y, br[j].x, br[j].y);
        }
    }
    double l = 0, r = 10000.0;
    while(r - l >= eps){
        double mid = (l + r) / 2;
        if(judge(mid))l = mid;
        else r = mid;
    }
    printf("%.9f\n", l);
}


int main(){
    work();
    return 0;
}