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; }