UVa-11159 : Factors and Multiples

問題概要

整数の集合A,B(濃度はいずれも100以下)がある。A、Bからいくつかの要素を除いて、Bの任意の要素がAのどの要素の倍数にもなっていないようにしたい。最小でいくつ取り除く必要があるか求める問題。

解法

二部グラフを構成すると、求めるものは最小点被覆であることが分かる。なので二部グラフであることから最大マッチングを求めてやればよいことが分かる。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 100;

int N, M;
int as[MAX_N], bs[MAX_N];

struct BM{

	static const int MAX_V = 2*MAX_N;
	int V;
	vector<int> graph[MAX_V];
	bool visited[MAX_V];
	int match[MAX_V];

	void clear(int V_){
		V = V_;
		for(int i=0; i<MAX_V; i++){
			graph[i].clear();
		}
	}

	void add_edge(int v, int u){
		graph[v].push_back(u);
		graph[u].push_back(v);
	}

	bool dfs(int v){
		visited[v] = true;
		for(int i=0; i<(int)graph[v].size(); i++){
			int u = graph[v][i], w = match[u];
			if(w < 0 || (!visited[w] && dfs(w))){
				match[u] = v;
				match[v] = u;
				return true;
			}
		}

		return false;
	}

	int bipartite_matching(){
		int ret = 0;
		memset(match, -1, sizeof(match));
		for(int i=0; i<V; i++)if(match[i] < 0){
			memset(visited, false, sizeof(visited));
			if(dfs(i)){
				ret++;
			}
		}

		return ret;
	}
};

BM bm;

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as + i);
	}

	scanf("%d", &M);
	for(int i=0; i<M; i++){
		scanf("%d", bs + i);
	}

	bm.clear(N+M);
}

int solve(){

	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(bs[j] == 0 || (as[i] != 0 && bs[j] % as[i] == 0)){
				bm.add_edge(i, j+N);
			}
		}
	}

	return bm.bipartite_matching();
}

int main(){
	int T;
	scanf("%d", &T);

	for(int i=0; i<T; i++){
		init();
		printf("Case %d: %d\n", i+1, solve());
	}

	return 0;
}