This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163" #include "../../template/template.hpp" #include "../../graph/flow/hungarian.hpp" 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, 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).first << endl; } }
#line 1 "test/verify/aoj-1163.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163" #line 1 "template/template.hpp" #include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { explicit FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } #line 4 "test/verify/aoj-1163.test.cpp" #line 1 "math/matrix/matrix.hpp" template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t size() const { if(A.empty()) return 0; assert(A.size() == A[0].size()); return A.size(); } size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector< T > &operator[](int k) const { return (A.at(k)); } inline vector< T > &operator[](int k) { return (A.at(k)); } static Matrix I(size_t n) { Matrix mat(n); for(int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(height()); while(k > 0) { if(k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } friend ostream &operator<<(ostream &os, Matrix &p) { size_t n = p.height(), m = p.width(); for(int i = 0; i < n; i++) { os << "["; for(int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() { Matrix B(*this); assert(width() == height()); T ret = 1; for(int i = 0; i < width(); i++) { int idx = -1; for(int j = i; j < width(); j++) { if(B[j][i] != 0) idx = j; } if(idx == -1) return (0); if(i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for(int j = 0; j < width(); j++) { B[i][j] /= vv; } for(int j = i + 1; j < width(); j++) { T a = B[j][i]; for(int k = 0; k < width(); k++) { B[j][k] -= B[i][k] * a; } } } return (ret); } }; #line 2 "graph/flow/hungarian.hpp" /** * @brief Hungarian(二部グラフの最小重み最大マッチング) * @docs docs/hungarian.md */ template< typename T > pair< T, vector< int > > hungarian(Matrix< T > &A) { const T infty = numeric_limits< T >::max(); const int N = (int) A.height(); const int M = (int) A.width(); 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], P}; } #line 6 "test/verify/aoj-1163.test.cpp" 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, 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).first << endl; } }