POJ-3692 : Kindergarten

問題概要

二つの完全グラフ(サイズ200以下)の間にいくつか辺がはられたようなグラフがある。最大クリークを求める問題。

解法

元のグラフのcomplementを考えると二部グラフになっていて最大独立集合を求めれば良いことが分かる。なので|最大独立集合|=|V|-|最小点被覆|=|V|-|最大マッチング|を求めれば良い。

acceptされたコード

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

const int MAX_N = 200;

int N, M;
bool graph[MAX_N][MAX_N];


struct BipartiteMatching{
	static const int MAX_V = 2*MAX_N;
	int V;
	vector<int> graph[MAX_V];
	int match[MAX_V];
	bool used[MAX_V];

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

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

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

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

	void set_V(int V_){
		V = V_;
	}
};

BipartiteMatching bm;

bool init(){
	int K;
	scanf("%d%d%d", &N, &M, &K);

	memset(graph, false, sizeof(graph));
	for(int i=0; i<K; i++){
		int x, y;
		scanf("%d%d",&x, &y);
		x--; y--;
		graph[x][y] = true;
	}

	return N > 0;
}

int solve(){
	bm.clear();
	bm.set_V(N+M);

	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++){
			if(!graph[i][j]){
				bm.add_edge(i, j+N);
			}
		}
	}

	return N + M - bm.bipartite_matching();
}

int main(){
	int c = 1;
	while(init()){
		printf("Case %d: %d\n", c++, solve());
	}

	return 0;
}