Codeforces Round #102 (Div. 1) B : Help General

問題概要

H*W(H,W<1000)の盤面にナイトを互いに衝突しないよう最大いくつ置くことができるか求める問題。

解法

同時に置くことができないふたつのマスの間に辺をはると二部グラフになっている。もとめたいものは最大独立集合なので、|V|-|最小点被覆|=|V|-|最大マッチング|で求められる。ただしグラフがそれなりに大きいので最大マッチングはhopcroft-karpを使うなどしないと間に合わない。なお、これで小さいケースを試すと法則性のようなものが確認できるので、場合分けO(1)で解けるらしい。

acceptされたコード

計算量O( sqrt(H*W) * (H*W) )。

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

const int MAX_N = 1000;

int H, W;

BipartiteMatching bm;

void init(){
	scanf("%d%d", &H, &W);
}

inline int get_idx(int h, int w){
	return h*W + w;
}

const int dy[] = {1, 2, -1, -2}, dx[] = {2, 1, 2, 1};

int solve(){

	bm.set_V(H*W);
	int e=0;
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			for(int k=0; k<4; k++){
				int ny = i + dy[k], nx = j + dx[k];
				if(0<=ny && ny<H && 0<=nx && nx<W){
					bm.add_edge(get_idx(i, j), get_idx(ny, nx));
					e+=2;
				}
			}
		}
	}
	bm.set_E(e);
	return H*W - bm.bipartite_matching();
}

int main(){

	init();
	printf("%d\n", solve());

	return 0;
}