Algoogle

Algorithm for Programming Contest

AOJ 2597 Color the Map Extreme

Category: AOJ Tag: aoj-icpc-advent-calendar-2015, geometry, maximal-independent-set

AOJ-ICPC Advent Calendar 2015の14日目の記事です.

Color the Map Extreme

問題概要


平面上にn(<=35)個多角形がある.彩色数を求めよ.

解法


幾何パートは辺同士で線分と点の距離が0になる個数と端点がくっついてるかでみてます.

  • 2個より多い: 辺がくっついてる
  • 2個で端点がくっついてない: 辺がくっついてる
  • それ以外: 辺がくっついてない

グラフができたら彩色数を求めます.
まず大前提として,できたグラフは平面グラフなので彩色数は最大でも4なので,グラフから極大独立集合を取ってきてそこの色を決めたら残りの部分は3色以下で塗れます.
極大独立集合とは互いに隣り合わない頂点の集合(独立集合)のうち,これ以上頂点を追加できないものです.
残ったグラフでは頂点がなければ0色,辺がなければ1色,2部グラフなら2色,それ以外なら3色とわかるので適当に塗っていけば何色で塗れるかわかります.
つまり極大独立集合を全列挙して試せばグラフの彩色数がわかります.

極大独立集合は貪欲にやっていけば求まりますが,列挙する場合は最小次数の頂点かその隣接する頂点を選ぶかでやるといい感じになります.
もうちょっとだけ詳しく書こうとしたけどわかりづらくなったので擬似コード.詳しくはコード見て下さい(FCCPCのチームライブラリから取ってきたので僕が書いたわけではありませんが).
前提条件として,SとTは空,Vはグラフの頂点集合が入ってます.事後条件はTは全ての極大独立集合の集合.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
set: S, T, V

func f
  if Vが空 then
    TにSを追加
  else then
    v = Vにある頂点のうち最小次数の頂点1つ
    Vからvとその近傍を取り除く(1)
    Sにvを入れる
    call f
    Sからvを取り除く
    Vに(1)で取り除いた頂点を戻す
    for w in Vにある頂点のうちvに隣接する頂点
      Vからwとその近傍を取り除く(2)
      Sにwを入れる
      call f
      Sからwを取り除く
      Vに(2)で取り除いた頂点を戻す
    end
  end
end

極大独立集合は最小の次数をkとしたとき (k+1)^(n/(k+1)) 個できる.これはk+1=eのとき最大になるが,kは整数なのでk+1=3の時が最大.
1つの極大独立集合を見つけるのにO(n)なので,列挙の計算量はO(n3^(n/3))となります.
ちなみにグラフによってはこのアルゴリズムは一部の極大独立集合を重複して列挙しますが,それを含めた計算量.

極大独立集合を除いたグラフでの彩色数のチェックにはそれぞれO(n)かかるので,全体の計算量もO(n3^(n/3)) となります.
35*3^(35/3)は10^7ぐらいなので間に合います.

コード


(2597.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>

namespace D2 {
const double eps = 1e-8;
struct point {
    double x, y;
    point():x(0),y(0) {}
    point(double x, double y):x(x),y(y) {}

    point operator+=(const point &p) { x+=p.x; y+=p.y; return *this; }
    point operator-=(const point &p) { x-=p.x; y-=p.y; return *this; }
    point operator+(const point &p) const { return point(*this)+=p; }
    point operator-(const point &p) const { return point(*this)-=p; }

    double norm() const { return x*x+y*y; }
    double abs() const { return sqrt(norm()); }
    double dot(const point &p) const { return x*p.x+y*p.y; }
    double cross(const point &p) const { return x*p.y-y*p.x; }
    point proj(const point &p) const { double k = dot(p)/norm(); return point(x*k,y*k); }
};
int ccw(point a, point b, point c) {
    b -= a, c -= a;
    if (b.cross(c) > eps)        return +1;
    if (b.cross(c) < -eps)       return -1;
    if (b.dot(c) < -eps)         return -2; // c -- a -- b
    if (b.norm() < c.norm()-eps) return +2; // a -- b -- c
    return 0;
}
struct line {
    point a, b;
    line(point a, point b) : a(a), b(b) {}

    point vec() const { return b-a; }
    double abs() const { return vec().abs(); }
    point proj(const point &p) const { return a+vec().proj(p-a); }
};
double dps(const point &p, const line &s) { return ccw(s.a,s.b,s.proj(p)) ? std::min((s.a-p).abs(), (s.b-p).abs()) : (s.proj(p)-p).abs(); }
}
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)

typedef vector<vector<int>> graph;
class maximal_indsets {
    const int n;
    const graph &G;
    vector<vector<int>> ret;
    vector<int> cur, exists, deg, block;
    void erase(int v) {
        if (exists[v]) {
            exists[v] = 0;
            for (int nv : G[v]) --deg[nv];
        }
    }
    void restore(int v) {
        exists[v] = 1;
        for (int nv : G[v]) ++deg[nv];
    }
    void select(int v) {
        cur.push_back(v);
        ++block[v], erase(v);
        for (int nv : G[v]) ++block[nv], erase(nv);
    }
    void unselect(int v) {
        cur.pop_back();
        --block[v], restore(v);
        for (int nv : G[v]) {
            if (--block[nv] == 0) restore(nv);
        }
    }
    void dfs() {
        int mn = n, v = -1;
        rep(u, n) if (exists[u]) {
            if (deg[u] < mn) mn = deg[u], v = u;
        }
        if (v == -1) {
            ret.push_back(cur);
        } else {
            select(v), dfs(), unselect(v);
            for (int nv : G[v]) {
                if (exists[nv]) select(nv), dfs(), unselect(nv);
            }
        }
    }
public:
    maximal_indsets(const graph& G) : n(G.size()), G(G), exists(n, 1), deg(n), block(n) {
        rep(v, n) deg[v] = G[v].size();
        dfs();
    }
    const vector<vector<int>>& get() const { return ret; }
};

int n, col[64];
graph G;
vector<vector<D2::point>> H;

bool touch(vector<D2::point> &s, vector<D2::point> &t) {
    int a = s.size(), b = t.size();
    rep(i,a) rep(j,b) {
        const D2::line p(s[i],s[(i+1)%a]), q(t[j],t[(j+1)%b]);
        int cnt = (D2::dps(p.a,q) < D2::eps) + (D2::dps(p.b,q) < D2::eps) +
                  (D2::dps(q.a,p) < D2::eps) + (D2::dps(q.b,p) < D2::eps);
        if(cnt > 2) return 1;
        if(cnt == 2) {
            if((p.a-q.a).abs() < D2::eps or (p.b-q.a).abs() < D2::eps or
               (p.a-q.b).abs() < D2::eps or (p.b-q.b).abs() < D2::eps) continue;
            return 1;
        }
    }
    return 0;
}

int dfs(int v) {
    int ex = 0;
    for(int &w: G[v]) if(col[w] >= 0) {
            ex |= 1<<col[w];
        }
    if((ex&3) == 3) {
        col[v] = 3;
        return 3;
    }
    if(ex&1) col[v] = 1;
    else col[v] = 0;
    ex |= 1<<col[v];
    int ret = __builtin_popcount(ex&3);
    for(int &w: G[v]) if(col[w] < 0) {
            int tmp = dfs(w);
            if(tmp == 3) return 3;
            ret = max(ret, tmp);
        }
    return ret;
}

int solve() {
    rep(i,n) repi(j,i+1,n) if(touch(H[i], H[j])) {
        G[i].push_back(j);
        G[j].push_back(i);
    }

    int ans = 4;
    auto ids = maximal_indsets(G).get();
    for(auto &xs: ids) {
        memset(col, -1, sizeof(col));
        for(int &v: xs) col[v] = 2;
        int need = 0;
        rep(i,n) if(col[i] < 0) need = max(need, dfs(i));
        ans = min(ans, need+1);
    }
    return ans;
}

bool input() {
    cin >> n;
    G.assign(n,vector<int>());
    H.assign(n,vector<D2::point>());
    int m; double x, y;
    rep(i,n) {
        cin >> m;
        rep(j,m) {
            cin >> x >> y;
            H[i].push_back(D2::point(x,y));
        }
    }
    return n;
}

int main(){
    while(input()) { cout << solve() << endl; }
    return 0;
}

Comments