minimum vertex cover problem (最小頂点被覆問題，近似アルゴリズム，焼きなましアルゴリズム(焼きなまし法とは異なります))

solveVertexCover.cpp

/*
最小頂点被覆の近似解を求める．
初めに線形時間で終わる2倍近似アルゴリズムを走らせ，そのあと，焼きなましで改善する．
*/

#include "bits/stdc++.h"

using namespace std;

#define TIME std::chrono::system_clock::now()
#define MILLISEC(t) (std::chrono::duration_cast<std::chrono::milliseconds>(t).count())

random_device noize;   // noize
mt19937 mt(noize());

int rand_int(int l, int h) {
    uniform_int_distribution<> range(l, h);
    return range(mt);
}

/*
============================
MINIMUM VERTEX COVER PROBLEM
============================
*/

// グラフクラス
class UndirectedGraphE {
public:
    size_t n;
    struct Edge {
        int u, v;
        Edge(int from = 0, int to = 0) :u(from), v(to) {}

        int to(int _v) { return _v == v ? u : v; }
    };
    vector<vector<int>> vertex_to;
    vector<Edge> edge;

    UndirectedGraphE(int n, int m = 5010) :n(n), vertex_to(n) { edge.reserve(m); }

    void connect(int from, int to) {
        vertex_to[from].push_back(edge.size()); // toto
        vertex_to[to].push_back(edge.size()); // fromfrom
        edge.emplace_back(from, to);
    }
    size_t degree(int v) {
        return vertex_to[v].size();
    }
};

// ==========================================================


// 頂点数
const int N_VERTICES = 2000;
// 辺の数
const int M_EDGES = 5000;

// 時間制限
const int TIMELIMIT = 1000; // [ms]



// グラフ集合
UndirectedGraphE graph(N_VERTICES);
// 頂点被覆集合
vector<int> vertexcover(N_VERTICES);


// vertexcoverが頂点被覆であることを検証する
bool verify() {
    int n = 0;
    vector<int> check(N_VERTICES, 0);
    for (int u = 0; u < N_VERTICES; ++u) {
        if (!vertexcover[u]) continue;
        if (!check[u]++) ++n;
        for (int ei : graph.vertex_to[u]) {
            auto e = graph.edge[ei];
            if (!check[e.to(u)]++) ++n;
        }
    }
    return (n == N_VERTICES);
}

// 頂点被覆集合の大きさ
int sizeof_vertexcover() {
    int c = 0;
    for (int i = 0; i < N_VERTICES; ++i)
        c += vertexcover[i];
    return c;
}

// ==========================================================


// グラフの情報と頂点被覆集合を出力する
void print_all() {

    printf("%d %d\n", N_VERTICES, M_EDGES);
    for (UndirectedGraphE::Edge& e : graph.edge) {
        printf("%d %d\n", e.u, e.v);
    }
    printf("vertex cover set is\n");
    for (int i = 0; i < N_VERTICES; ++i)
        if (vertexcover[i])
            printf("%d ", i);
    printf("\n");

    printf("verified? => %d\n", verify());

}


// 頂点被覆集合のサイズと検証結果のみを表示
void print_easy() {
    printf("size of vertex cover set is %d\n", sizeof_vertexcover());
    printf("verified? => %d\n", verify());
}

// ==========================================================


// 辺をランダムに生成する
// 実装が雑
void edgeGenerator(UndirectedGraphE& graph, int m) {
    int n = graph.n;
    set<pair<int, int>> used;
    while (m--) {
        // 良い乱数生成方法では無いけれども，即席で
        int a = rand_int(1, n - 1);
        int b = rand_int(0, n - 2);
        if (a == b) ++b;
        if (a > b) swap(a, b);
        if (used.count(make_pair(a, b))) { ++m; continue; }
        used.insert(make_pair(a, b));
        graph.connect(a, b);
    }
}

// ==========================================================


// 線形時間で終わる2倍近似アルゴリズム
void solve_approximate_linear() {
    int i, k;

    vector<int> vscore(N_VERTICES);
    for (i = 0; i < N_VERTICES; ++i)
        vscore[i] = graph.degree(i);

    for (UndirectedGraphE::Edge& e : graph.edge) {
        k = min(vscore[e.u], vscore[e.v]);
        vscore[e.u] -= k;
        vscore[e.v] -= k;
    }

    for (i = 0; i < N_VERTICES; ++i)
        vertexcover[i] = (vscore[i] == 0);
}


// 時間を決めて動作させ続ける近似アルゴリズム
void solve_approximate_fixed() {
    auto begintime = TIME;

    // 最も良い結果を保持しておく
    int bestresult_score    = sizeof_vertexcover();
    // 最も良い結果を保持しておく
    vector<int> bestresult  = vertexcover;
    

    // 現在のスコア
    int score = bestresult_score;

    vector<int> q;
    while (MILLISEC(TIME - begintime) < TIMELIMIT) {
        // 適当な頂点を選ぶ
        int b = rand_int(0, N_VERTICES - 1);

        // 頂点被覆として選ばれていないなら再抽選
        if (!vertexcover[b]) continue;

        // リストに加える
        q.emplace_back(b);

        int cooldown = 0;
        while (!q.empty()) {
            // リストからランダムに頂点を選ぶ
            int i = rand_int(0, q.size() - 1);
            int v = q[i];
            // リストから選んだ頂点を除外
            swap(q[i], q[q.size() - 1]); q.pop_back();

            // 頂点被覆として選ばれていないなら再抽選
            if (!vertexcover[v]) continue;

            // その頂点がどの辺にも接続しないなら再抽選
            if (graph.degree(v) == 0) continue;

            // 一旦その頂点を頂点被覆集合から取り除く．
            vertexcover[v] = 0;
            --score;

            // この操作によって一部のvに接続する辺はどの頂点からも被覆されないかもしれない．
            // 隣接する頂点を選択することによって，頂点被覆を維持する
            for (int eidx : graph.vertex_to[v]) {
                // 接続する辺
                auto edge = graph.edge[eidx];
                // 隣接する頂点
                int u = edge.to(v);

                // v,uが頂点被覆集合に含まれない <=> 辺{v,u}は被覆されていない
                if (!vertexcover[u]) {
                    // uを頂点被覆集合に追加する
                    vertexcover[u] = 1;
                    ++score;

                    // uをリストに追加する
                    // 現在のvが再びuとして選ばれてしまうが，気にしない
                    q.push_back(u);
                }
            }
            // 今の状態よりも良いならば
            if (score < bestresult_score) {
                // 今の状態が最良
                bestresult_score = score;
                bestresult = vertexcover;

                cooldown = 0;
            }
            ++cooldown;

            // より良い状態が見えてこないなら
            if (100 < cooldown) {
                // 最良の状態に戻して，再抽選．
                score = bestresult_score;
                vertexcover = bestresult;
                break;
            }
        }
    }
}

// ==========================================================

int main() {
    int i, j, k;
    int x, y, a, b;


    edgeGenerator(graph, M_EDGES);

    // 簡単な近似アルゴリズムを動かす．
    solve_approximate_linear();

    print_easy();

    // 一定時間近似アルゴリズムを動かす．
    solve_approximate_fixed();

    print_easy();


    //print_all();

    return 0;
}