説明

二部グラフの最小重み最大マッチングを求める。

計算量

  • $O(N^2 M)$

実装例

  • hungarian($A$):= 重み行列 $A$ の最小重み最大マッチングを返す。最大重みを求めたいときは重み行列の重みを $-1$ 倍する。行列 $A$ は 1-indexed で $N \le M$ を満たす必要があることに注意すること。
template< typename T >
T hungarian(Matrix< T > &A) {
  const T infty = numeric_limits< T >::max();
  const int N = (int) A.size();
  const int M = (int) A[0].size();
  vector< int > P(M), way(M);
  vector< T > U(N, 0), V(M, 0), minV;
  vector< bool > used;

  for(int i = 1; i < N; i++) {
    P[0] = i;
    minV.assign(M, infty);
    used.assign(M, false);
    int j0 = 0;
    while(P[j0] != 0) {
      int i0 = P[j0], j1 = 0;
      used[j0] = true;
      T delta = infty;
      for(int j = 1; j < M; j++) {
        if(used[j]) continue;
        T curr = A[i0][j] - U[i0] - V[j];
        if(curr < minV[j]) minV[j] = curr, way[j] = j0;
        if(minV[j] < delta) delta = minV[j], j1 = j;
      }
      for(int j = 0; j < M; j++) {
        if(used[j]) U[P[j]] += delta, V[j] -= delta;
        else minV[j] -= delta;
      }
      j0 = j1;
    }
    do {
      P[j0] = P[way[j0]];
      j0 = way[j0];
    } while(j0 != 0);
  }
  return -V[0];
}

検証

AOJ 1163 Cards

int main() {
  int M, N, B[500], R[500];
  while(cin >> M >> N, M) {
    for(int i = 0; i < M; i++) {
      cin >> B[i];
    }
    for(int i = 0; i < N; i++) {
      cin >> R[i];
    }
    if(M > N) swap(M, N), swap(B, R);
    Matrix< int > mat(M + 1, vector< int >(N + 1));
    for(int i = 0; i < M; i++) {
      for(int j = 0; j < N; j++) {
        if(__gcd(B[i], R[j]) > 1) mat[i + 1][j + 1] = -1;
      }
    }
    cout << -hungarian(mat) << endl;
  }
}