fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Hopcroft-Karp algorithm: Fast bipartite matching
  5. // Returns maximum matching between left side (nl nodes) and right side (nr nodes)
  6. int maxMatch(vector<vector<int>>& g, int nl, int nr) {
  7.     const int INF = 1e9;
  8.     vector<int> ml(nl, -1), mr(nr, -1), lv(nl);
  9.     // ml[u] = which right node is u matched to (-1 if unmatched)
  10.     // mr[v] = which left node is v matched to (-1 if unmatched)
  11.     // lv[u] = level of left node u in BFS layering
  12.  
  13.     // Build level graph using BFS from unmatched left nodes
  14.     auto bfs = [&]() {
  15.         queue<int> q;
  16.         for (int u = 0; u < nl; u++) {
  17.             if (ml[u] == -1) {
  18.                 lv[u] = 0;  // Start from unmatched nodes
  19.                 q.push(u);
  20.             } else {
  21.                 lv[u] = INF;
  22.             }
  23.         }
  24.  
  25.         bool ok = false;  // Did we reach any unmatched right node?
  26.         while (!q.empty()) {
  27.             int u = q.front();
  28.             q.pop();
  29.  
  30.             for (int v : g[u]) {
  31.                 int p = mr[v];  // Who is v matched to?
  32.                 if (p != -1 && lv[p] == INF) {
  33.                     lv[p] = lv[u] + 1;  // Set level
  34.                     q.push(p);
  35.                 }
  36.                 if (p == -1) ok = true;  // Found unmatched right node
  37.             }
  38.         }
  39.         return ok;
  40.     };
  41.  
  42.     // DFS to find augmenting paths in level graph
  43.     function<bool(int)> dfs = [&](int u) {
  44.         for (int v : g[u]) {
  45.             int p = mr[v];
  46.             // Either v is unmatched, or follow alternating path
  47.             if (p == -1 || (lv[p] == lv[u] + 1 && dfs(p))) {
  48.                 ml[u] = v;
  49.                 mr[v] = u;
  50.                 return true;  // Found augmenting path
  51.             }
  52.         }
  53.         lv[u] = INF;  // Mark as processed
  54.         return false;
  55.     };
  56.  
  57.     int res = 0;
  58.     // Repeat: build levels, then find all augmenting paths
  59.     while (bfs()) {
  60.         for (int u = 0; u < nl; u++) {
  61.             if (ml[u] == -1 && dfs(u)) {
  62.                 res++;
  63.             }
  64.         }
  65.     }
  66.     return res;
  67. }
  68.  
  69. int main() {
  70.     ios::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.  
  73.     int n, k;
  74.     cin >> n >> k;
  75.  
  76.     // Problem: n cats and n mice at different positions
  77.     // Select K animals total (some cats + some mice)
  78.     // Minimize the maximum distance between any selected cat and selected mouse
  79.  
  80.     vector<pair<int, int>> cat(n), mouse(n);
  81.  
  82.     for (int i = 0; i < n; i++) {
  83.         cin >> cat[i].first >> cat[i].second;
  84.     }
  85.     for (int i = 0; i < n; i++) {
  86.         cin >> mouse[i].first >> mouse[i].second;
  87.     }
  88.  
  89.     // Precompute squared distances (avoid sqrt)
  90.     vector<vector<long long>> d2(n, vector<long long>(n));
  91.     vector<long long> vals;
  92.  
  93.     for (int i = 0; i < n; i++) {
  94.         for (int j = 0; j < n; j++) {
  95.             long long dx = cat[i].first - mouse[j].first;
  96.             long long dy = cat[i].second - mouse[j].second;
  97.             long long dist = dx * dx + dy * dy;
  98.             d2[i][j] = dist;
  99.             vals.push_back(dist);
  100.         }
  101.     }
  102.  
  103.     // Get unique sorted distances for binary search
  104.     sort(vals.begin(), vals.end());
  105.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  106.  
  107.     // Key idea: For maximum distance threshold D:
  108.     // Build bipartite graph of "BAD" edges where dist(cat, mouse) > D
  109.     // Need to select K animals with NO bad edges between selected cats/mice
  110.     // = independent set of size K in bipartite graph
  111.     // In bipartite: maxIndependentSet = 2n - maxMatching
  112.     // Feasible if: 2n - maxMatching >= K, i.e., maxMatching <= 2n - K
  113.     auto check = [&](long long D) -> bool {
  114.         // Build bipartite graph: edge if distance > D (BAD edge)
  115.         vector<vector<int>> g(n);
  116.  
  117.         for (int i = 0; i < n; i++) {
  118.             for (int j = 0; j < n; j++) {
  119.                 if (d2[i][j] > D) {  // BAD edge (too far apart)
  120.                     g[i].push_back(j);
  121.                 }
  122.             }
  123.         }
  124.  
  125.         // Find max matching in BAD edges graph
  126.         int m = maxMatch(g, n, n);
  127.  
  128.         // Can we select K animals avoiding all bad edges?
  129.         // Max independent set = 2n - m
  130.         return (2 * n - m) >= k;
  131.     };
  132.  
  133.     // Binary search for minimum possible maximum distance
  134.     int l = 0, r = vals.size() - 1;
  135.  
  136.     while (l < r) {
  137.         int mid = (l + r) / 2;
  138.  
  139.         if (check(vals[mid])) {
  140.             r = mid;  // Can achieve this threshold, try smaller
  141.         } else {
  142.             l = mid + 1;  // Need bigger threshold
  143.         }
  144.     }
  145.  
  146.     // Convert squared distance back to actual distance
  147.     double ans = sqrt((double)vals[l]);
  148.  
  149.     cout << fixed << setprecision(12) << ans << "\n";
  150.  
  151.     return 0;
  152. }
Runtime error #stdin #stdout 2.07s 2096000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4H0nQG
language:
C++14 (gcc 8.3)
created:
115 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!