BZOJ2663 [Beijing wc2012]灵魂宝石

2018 年 03 月 14 日发布.

Description

平面中有$n$个黑点和$n$个白点。这些点组成$n$对，但是你不知道它们的对应关系。若某队中黑点白点距离$<R$，则它是好的；$>R$则不是好的；$=R$的时候可好可不好。已知有$k$对是好的，求$R$的最大值和最小值。

Solution

首先解决对称的问题：给定$R$，求$k$的最大值和最小值。

求$k$的最大值可以二分图匹配：所有$\leqslant R$的可以构成一对。

求最小值同样可以二分图匹配：所有$\geqslant R$的可以构成一对（不好的一对）；令不好的尽量多即可。

可以发现当$R$增大时$k_{max}$和$k_{min}$都是不减的。所以二分$R$即可。

Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
const int N = 55;
int X[N], Y[N], x[N], y[N];
int n, K, R;
inline int sqr(int x) { return x * x; }
bool check(int i, int j, bool max) {
  int l = sqr(X[i] - x[j]) + sqr(Y[i] - y[j]);
  return max ? l >= R : l <= R;
}
int my[N];
bool vis[N];
bool dfs(int x, bool max) {
  for (int y = 1; y <= n; ++y) if (!vis[y]) {
    bool l = check(x, y, max);
    if (!l) continue;
    vis[y] = true;
    if (!my[y] || dfs(my[y], max)) {
      my[y] = x;
      return true;
    }
  }
  return false;
}
bool check(int mid, bool max) {
  R = mid;
  memset(my, 0, sizeof my);
  int ans = 0;
  for (int x = 1; x <= n; ++x) {
    memset(vis, 0, sizeof vis);
    if (dfs(x, max)) ++ans;
  }
  return max ? n - ans <= K : ans >= K;
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; ++i) scanf("%d%d", &X[i], &Y[i]);
  for (int i = 1; i <= n; ++i) scanf("%d%d", &x[i], &y[i]);
  int l = 0, r = 10000000;
  while (l < r) {
    int mid = (l + r) / 2;
    if (check(mid, false)) r = mid;
    else l = mid + 1;
  }
  printf("%.2lf ", sqrt(l));
  if (K == n) { puts("+INF"); return 0; }
  l = 0, r = 10000000;
  while (l < r) {
    int mid = r + (l - r) / 2;
    if (check(mid, true)) l = mid;
    else r = mid - 1;
  }
  printf("%.2lf\n", sqrt(l));
  return 0;
}