AOJ 2136 Webby Subway

問題

n個の地下鉄をk層に分けたい。
それぞれの地下鉄は、折れ線で表される。


同じ層の地下鉄は、共有点を持ってはならないものとするとき、
最小で何層に分ければよいか、求めよ。

制約条件

n≦22
折れ線は30本以下の線分の集まりとして表される。

方針

共有点を持つ線分同士を線で結ぶと、
無向グラフができる。


このグラフの彩色数が求める答えである。
あるグラフがk-彩色可能かどうかは包除原理を使ってO(2^n * n)時間で求められる。
(wataさんの指数時間アルゴリズムのスライド参照)


少し時間がきついので、あんまり計算を適当にやるとTLE。

ソースコード

int n, N[30];
bool e[30][30];

bool is(const G &l, const G&m){
	rep(i, l.size() - 1) rep(j, m.size() - 1){
		if(intersectSS(L(l[i], l[i + 1]), L(m[j], m[j + 1])))
		return 1;
	}
	return 0;
}

const int mod = 10009;

int I[1 << 22];
inline int modpow(int n, int m){
	int res = 1;
	for(; m; m >>= 1){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
bool color(int k){
	ll ans = 0;
	rep(i, 1 << n){
		if(__builtin_popcount(i) % 2) ans -= modpow(I[i], k);
		else ans += modpow(I[i], k);
	}
	ans = (ans % mod + mod) %  mod;
	
	return ans;
}

int main(){
	while(cin >> n, n){
		vector<G> ls;
		rep(i, n){
			int m;
			cin >> m;
			G ps;
			rep(j, m){
				int x, y;
				cin >> x >> y;
				ps.pb(P(x, y));
			}
			ls.pb(ps);
		}
		rep(i, n) rep(j, i) e[i][j] = e[j][i] = is(ls[i], ls[j]);
		rep(i, n){
			int bit = 1 << i;
			rep(j, n) if(e[i][j]) bit |= 1 << j;
			N[i] = bit;
		}
		rep(i, 1 << n) I[i] = 0;
		I[0] = 1;
		for(int i = 1; i < 1 << n; i++){
			int v = 0;
			for(; !(i & 1 << v); v++);
			I[i] = I[i - (1 << v)] + I[i & ~N[v]];
			if(I[i] > mod) I[i] -= mod;
		}
		
		int lo = 0, hi = n, mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			if(color(mid)) hi = mid;
			else lo = mid;
		}
		cout << hi << endl;
	}
	return 0;
}