AOJ1163

AOJ1163

解くのは初めてではないんだけど、何となくフローを描いてみたくなったのでやってみた。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

struct E {
  int src, dst;
  E(int s, int d) : src(s), dst(d) {}
};

const int RED = 500 + 1;
const int BLUE = 500 + 1;

const int V = RED + BLUE + 2;

vector<E> g[V];
bool vis[V];

int c[V][V];
int path[V];

bool rec(int node, int snk)
{
  vis[node] = true;
  if (node == snk) return true;

  for (int i = 0; i < (int)g[node].size(); ++i) {
    E e = g[node][i];
    if (vis[e.dst] || c[e.src][e.dst] <= 0) continue;
    path[e.dst] = e.src;
    if (rec(e.dst, snk)) return true;
  }

  return false;
}

int flow(int src, int snk)
{
  fill(path, path + V, 0);

  int sum = 0;
  while (rec(src, snk)) {
    fill(vis, vis + V, false);
    for (int i = snk; path[i]; i = path[i]) {
      --c[path[i]][i];
      ++c[i][path[i]];
    }
    ++sum;
  }

  return sum;
}


int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}

int main(int argc, char *argv[])
{
  int red, blue;
  while (cin >> red >> blue && (red | blue)) {

    fill(g, g + V, vector<E>());
    fill(&c[0][0], &c[V - 1][V], 0);
    fill(vis, vis + V, false);

    int r[red];
    for (int i = 0; i < (int)red; ++i) {
      cin >> r[i];
    }

    int b[blue];
    for (int i = 0; i < (int)blue; ++i) {
      cin >> b[i];
    }

    const int R = 0, B = 1;
    map<int, int> name[2];
    int cnt = 1;

    for (int i = 0; i < (int)red; ++i) {
      name[R][i] = cnt++;
    }

    for (int i = 0; i < (int)blue; ++i) {
      name[B][i] = cnt++;
    }

    const int src = cnt++;
    const int snk = cnt++;

    for (int i = 0; i < (int)red; ++i) {
      for (int j = 0; j < (int)blue; ++j) {
        int n = gcd(max(r[i], b[j]), min(r[i], b[j]));
        if (n != 1) {
          int a = name[R][i];
          int b = name[B][j];
          g[a].push_back(E(a, b));
          g[b].push_back(E(b, a));
          c[a][b] = 1;
        }
      }
    }

    for (int i = 0; i < (int)red; ++i) {
      int n = name[R][i];
      g[src].push_back(E(src, n));
      c[src][n] = 1;
    }
    for (int i = 0; i < (int)blue; ++i) {
      int n = name[B][i];
      g[n].push_back(E(n, snk));
      c[n][snk] = 1;
    }

    cout << flow(src, snk) << endl;
  }
  return 0;
}