换一张图比值顶到 2

换一张图：三条互不相连的边。贪心和最优各要几个点？

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

using Edge = pair<int, int>;

int greedy_vc(const vector<Edge>& edges) {    // 贪心：两头都没被盖住就把两头都收下，返回收了几个点
    vector<bool> used(16, false);
    int cnt = 0;
    for (auto [a, b] : edges) {
        if (!used[a] && !used[b]) {
            used[a] = used[b] = true;
            cnt += 2;
        }
    }
    return cnt;
}

int opt_vc(const vector<Edge>& edges, int n) {  // 暴力：从小到大试每种规模，第一个能盖住所有边的就是最优
    for (int k = 0; k <= n; k++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != k) continue;
            bool ok = true;
            for (auto [a, b] : edges) {
                if (!((mask >> a) & 1) && !((mask >> b) & 1)) { ok = false; break; }
            }
            if (ok) return k;
        }
    }
    return n;
}

const vector<Edge> E = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}, {4, 5}, {5, 6}, {4, 6}};
const vector<Edge> E2 = {{0, 1}, {2, 3}, {4, 5}};

int main() {
    cout << greedy_vc(E2) << "/" << opt_vc(E2, 6) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）