SRM477 Div1 Medium

500

2部マッチングするだけ。
入力の仕様に殺意を覚えた。1時間も悩んだ。

const int N = 500 + 10;
vector<int> g[N];

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

void add_edge(int src, int dst)
{
  dst += (N / 2);
  g[src].push_back(dst);
  g[dst].push_back(src);
  return ;
}

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

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

int gcd(int a, int b)
{
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  else return gcd(b, a % b);
}

bool valid(lli a, lli b)
{
  if (gcd(a, b) != 1) return false;
  lli x = a * a + b * b;
  lli c = (lli)ceil(sqrt((double)x));
  lli d = (lli)floor(sqrt((double)x));
  return (c * c == x) && (d * d == x);
}

class PythTriplets {
public:
  int findMax(vector <string> stick)
  {
    fill(g, g + N, vector<int>());

    vector<int> ls;
    istringstream iss(accumulate(stick.begin(), stick.end(), string("")).c_str());
    for (int n; iss >> n; ls.push_back(n)) ;
    sort(ls.begin(), ls.end());

    for (int i = 0; i < ls.size(); ++i) {
      for (int j = 0; j < ls.size(); ++j) {
        if (valid(ls[i], ls[j])) add_edge(i, j);
      }
    }
    return matching() / 2;
  }
};