两张图的近似比

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

两张图各算一次近似比，用整数表示（放大 100 倍），再验一次两者都没超过 2 倍。输出如 150/200/都没超。

（本题用 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) {
        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() {
    // TODO: 两张图各算一次「贪心个数 * 100 / 最优个数」（先乘后除）
    int a = -1, b = -1;
    // TODO: 两个比值都不超过 200 就是「都没超」
    string verdict = "超了";
    cout << a << "/" << b << "/" << verdict << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

两张图的近似比

更多题目

全部评论