SRM549 Div2 Medium

500

マッチング。

const int TOP = 100 + 5;
const int BOT = 100 + 5;

const int N = TOP + BOT + 5;

vector<int> g[N];

int match[N];
bool vis[N];

bool rec(int curr)
{
  vis[curr] = true;
  for (int i = 0; i < g[curr].size(); ++i) {
    int next = g[curr][i];
    int w = match[next];
    if (w < 0 || (!vis[w] && rec(w))) {
      match[curr] = next;
      match[next] = curr;
      return true;
    }
  }
  return false;
}

int matching(int n)
{
  int f = 0;
  fill(match, match + N, -1);
  for (int i = 0; i < n; ++i) {
    if (match[i] < 0) {
      fill(vis, vis + N, false);
      f += rec(i);
    }
  }
  return f;
}

class PointyWizardHats {
public:
  int getNumHats(vector <int> tH,
                 vector <int> tR,
                 vector <int> bH,
                 vector <int> bR)
  {
    fill(g, g + N, vector<int>());
    fill(vis, vis + N, false);

    const int T = tH.size();
    const int B = bH.size();

    const double eps = 1e-8;

    for (int i = 0; i < T; ++i) {
      for (int j = 0; j < B; ++j) {
        double tA = (double)tR[i] / sqrt(tR[i] * tR[i] + tH[i] * tH[i]);
        double bA = (double)bR[j] / sqrt(bR[j] * bR[j] + bH[j] * bH[j]);
        if (tA + eps < bA && tR[i] < bR[j]) {
          int a = i;
          int b = j + TOP;
          g[a].push_back(b);
          g[b].push_back(a);
        }
      }
    }

    return matching(T);
  }
};