verify/aizu/aizu-1163.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/flows/hungarian.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, n;
	while (cin >> m >> n, m) {
		vector<int> b(m);
		for (int i = 0; i < m; ++i) {
			cin >> b[i];
		}
		vector<int> r(n);
		for (int i = 0; i < n; ++i) {
			cin >> r[i];
		}
		if (m > n) {
			swap(m, n);
			swap(b, r);
		}
		vector<vector<int>> v(m, vector<int>(n));
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (gcd(b[i], r[j]) > 1) {
					v[i][j] = -1;
				}
			}
		}
		cout << -hungarian(v).first << '\n';
	}
}

// another instance of use below


// int main() {

// 	using namespace std;

// 	int n; cin >> n;

// 	vector<vector<long long>> a(n, vector<long long>(n));

// 	for (int i = 0; i < n; i++)

// 		for (int j = 0; j < n; j++) cin >> a[i][j];

// 	auto res = hungarian(a);

// 	vector<int> loc(n);

// 	for (int i = 0; i < n; i++) {

// 		loc[res.second[i]] = i;

// 	}

// 	cout << res.first << '\n';

// 	for (int x : loc) 

// 		cout << x << " ";

// 	cout << '\n';

// 	return 0;

// }

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class C> std::pair<C, std::vector<int>> hungarian(const std::vector<std::vector<C>>& a_) {
	const C INF = std::numeric_limits<C>::max();
	int n = (int)a_.size();
	int m = (int)a_[0].size();
	assert(n <= m);
	std::vector<std::vector<C>> a(n + 1, std::vector<C>(m + 1, 0));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			a[i + 1][j + 1] = a_[i][j];
	std::vector<C> u(n + 1), v(m + 1);
	std::vector<int> job(m + 1);
	for (int i = 1; i <= n; i++) {
		int w = 0;
		job[w] = i;
		std::vector<C> dist(m + 1, INF);
		std::vector<int> pre(m + 1, -1);
		std::vector<bool> done(m + 1);
		while (job[w]) {
			done[w] = 1;
			int j = job[w], nxt;
			C delta = INF;
			for (int ww = 0; ww <= m; ww++) {
				if (!done[ww]) {
					if (dist[ww] > a[j][ww] - u[j] - v[ww]) {
						dist[ww] = a[j][ww] - u[j] - v[ww];
						pre[ww] = w; 
					}
					if (delta > dist[ww]) {
						delta = dist[ww];
						nxt = ww;
					}
				}
			}
			for (int ww = 0; ww <= m; ww++) {
				if (done[ww]) {
					u[job[ww]] += delta;
					v[ww] -= delta;
				} else {
					dist[ww] -= delta;
				}
			}
			w = nxt;
		}
		for (int ww; w; w = ww) 
			job[w] = job[ww = pre[w]];
	}
	job.erase(job.begin());
	for (int i = 0; i < m; i++)
		job[i]--;
	return {-v[0], job};
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int m, n;
	while (cin >> m >> n, m) {
		vector<int> b(m);
		for (int i = 0; i < m; ++i) {
			cin >> b[i];
		}
		vector<int> r(n);
		for (int i = 0; i < n; ++i) {
			cin >> r[i];
		}
		if (m > n) {
			swap(m, n);
			swap(b, r);
		}
		vector<vector<int>> v(m, vector<int>(n));
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (gcd(b[i], r[j]) > 1) {
					v[i][j] = -1;
				}
			}
		}
		cout << -hungarian(v).first << '\n';
	}
}

// another instance of use below


// int main() {

// 	using namespace std;

// 	int n; cin >> n;

// 	vector<vector<long long>> a(n, vector<long long>(n));

// 	for (int i = 0; i < n; i++)

// 		for (int j = 0; j < n; j++) cin >> a[i][j];

// 	auto res = hungarian(a);

// 	vector<int> loc(n);

// 	for (int i = 0; i < n; i++) {

// 		loc[res.second[i]] = i;

// 	}

// 	cout << res.first << '\n';

// 	for (int x : loc) 

// 		cout << x << " ";

// 	cout << '\n';

// 	return 0;

// }