AOJ 2558 Medical Inspection - すいバカ日誌

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2558

解法

最小点被覆は多項式時間で解けない．
この時点で，グラフにある良い性質を用いるか，頑張って枝刈りしかない．
しかし与えられたグラフは単純グラフであるだけで他にいい感じの性質がない．
よって，泣きながら枝刈りを書く．

枝刈りの戦略は以下のようにした．何が良いかよくわからないけど．

次数が k + 1 以上なら使わなければ死ぬので最初から使っておく（これは絶対必要）
探索するときは，次数の多い方から選んでいくほうが嬉しそう？（これがどれぐらい寄与してるかよくわからない）
注目している頂点を使わない場合は，隣接頂点をすべて使うのが確定する．なので，この時点で隣接頂点すべてを削除しておくこと．（自分はこれを忘れていてTLE喰らいまくった）
上記の戦略で探索していくなら，次数1のやつはスキップするのがよい．どうせ後でいい感じに消えるし，次数1だけのために貴重な k を使って探索空間を広げても嬉しくない．
探索過程で，(使える残りの数) * (余ってる頂点で最大の次数) < (残ってる辺の数) ならどうやっても無理なのでこれも枝刈り（これも多分必要だと思う）．

結局 0.05sec で通った．
なんか調べてみたら，O(1.3^k + kn) ぐらいで解く指数時間アルゴリズムがあるらしい．やばそう．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<set<int>> g(n);
    vector<int> deg(n);
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].insert(b - 1);
        g[b - 1].insert(a - 1);
        deg[a - 1]++;
        deg[b - 1]++;
    }

    vector<bool> used(n);
    int now = 0;
    for(int i = 0; i < n; ++i) {
        if(deg[i] > k) {
            used[i] = true;
            deg[i] = 0;
            now++;
            for(auto to : g[i]) {
                deg[to]--;
            }
        }
    }
    int remain_edge = 0;
    for(int i = 0; i < n; ++i) {
        remain_edge += deg[i];
    }
    remain_edge /= 2;
    if(now > k) {
        cout << "Impossible" << endl;
        return 0;
    }

    vector<int> ord;
    {
        vector<set<int>> g2(n - now);
        deg.assign(n - now, 0);
        int x = 0;
        vector<int> idx(n);
        vector<pii> deg_idx;
        for(int i = 0; i < n; ++i) {
            if(used[i]) continue;
            deg[x] = 0;
            idx[i] = x++;
        }
        for(int i = 0; i < n; ++i) {
            if(used[i]) continue;
            for(auto to : g[i]) {
                if(!used[to]) {
                    deg[idx[i]]++;
                    g2[idx[i]].insert(idx[to]);
                }
            }
            deg_idx.emplace_back(deg[idx[i]], idx[i]);
        }
        sort(rbegin(deg_idx), rend(deg_idx));
        for(auto& p : deg_idx) {
            ord.push_back(p.second);
        }
        g = move(g2);
        n = g.size();
    }

    int ans = k + 1;
    function<void(int)> solve = [&](int i) {
        if(i == n) {
            ans = min(ans, now);
            return;
        }
        const int r = min(k - now, n - i);
        const int v = ord[i];
        if(now >= ans || now > k || remain_edge > r * deg[v]) {
            return;
        };
        if(g[v].empty()) {
            solve(i + 1);
        } else {
            // use
            if((int)g[v].size() > 1) {
                now++;
                vector<int> erased;
                for(auto to : g[v]) {
                    erased.push_back(to);
                    g[to].erase(v);
                }
                remain_edge -= (int)g[v].size();
                g[v].clear();
                solve(i + 1);
                for(auto to : erased) {
                    g[v].insert(to);
                    g[to].insert(v);
                }
                remain_edge += (int)g[v].size();
                now--;
            }

            // not use
            if(now + (int)g[v].size() <= min(ans, k)) {
                now += g[v].size();
                vector<int> erased;
                vector<set<int>> erased2;
                set<pii> erased_edges;
                for(auto to : g[v]) {
                    erased.push_back(to);
                    set<int> tmp;
                    for(auto to2 : g[to]) {
                        tmp.insert(to2);
                        erased_edges.emplace(min(to, to2), max(to, to2));
                        if(to2 != v) {
                            g[to2].erase(to);
                        }
                    }
                    g[to].clear();
                    erased2.push_back(move(tmp));
                }
                remain_edge -= erased_edges.size();
                g[v].clear();
                solve(i + 1);
                for(int j = 0; j < (int)erased.size(); ++j) {
                    g[v].insert(erased[j]);
                    for(auto to2 : erased2[j]) {
                        g[to2].insert(erased[j]);
                    }
                    g[erased[j]] = move(erased2[j]);
                    remain_edge += g[erased[j]].size();
                }
                now -= g[v].size();
            }
        }
    };
    solve(0);

    if(ans > k) {
        cout << "Impossible" << endl;
    } else {
        cout << ans << endl;
    }
}

感想

実装方針失敗してそう．本番ならもうちょっと高速化サボって実装をスマートにしたほうが良い？
正直枝刈りの実行時間なんて僕には見積もれないんですが……．枝刈り対策どうすればええんや……．毎回お気持ちで書いてしまっていてつらい．