写出 2-近似的顶点覆盖

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

补全贪心：挨条边看，两头都没被盖住就把两头一起收下。输出「贪心个数/最优个数」。

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

提交你的答案

请登录后提交答案。

去登录

← 换一张图比值顶到 2 两张图的近似比 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#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) {
        // TODO: 这条边两头都还没被盖住，就把两头都标成 used，cnt 加 2
        (void)a; (void)b;
    }
    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(E) << "/" << opt_vc(E, 7) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

写出 2-近似的顶点覆盖

更多题目

全部评论