轻松的编程学习
首页
题库
学习路径
在线商城
能力地图
下载应用
登录 / 注册
菜单
🔴 两张图的近似比，都没超过 2
👁️ 0 人浏览
💬 0 人评论
❤️ 添加收藏
两张图（本节主图 和 三条独立边）各算一次近似比，用整数表示（放大 100 倍），再验一次两者都没超过 2 倍。
提交你的答案
请登录后提交答案。
去登录
← 自己写：2-近似的顶点覆盖
⚠️ 最优要试多少个子集 →
更多题目
让程序说出"你好"
让程序欢迎你
哪个命令能显示内容
哪里是指令，哪里是结果
让程序说出你的名字
这个程序会显示什么
代码编辑器
语言：
python3
c11
cpp17
Ctrl
+
Enter
运行
👩🏫 AI
▶ 运行代码
重置代码
打印代码
from itertools import combinations E = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (4, 6)] V = [0, 1, 2, 3, 4, 5, 6] def greedy_vc(edges): """贪心：挨个看边，两头都没被盖住就把两头都收进来""" cover, used = [], set() for a, b in edges: if a not in used and b not in used: cover += [a, b] used |= {a, b} return sorted(cover) def opt_vc(edges, vs): """暴力：从小到大试每一种规模，第一个能盖住所有边的就是最优""" for k in range(len(vs) + 1): for c in combinations(vs, k): s = set(c) if all(a in s or b in s for a, b in edges): return sorted(s) return sorted(vs) E2 = [(0, 1), (2, 3), (4, 5)] V2 = [0, 1, 2, 3, 4, 5] # TODO: 两张图各算一次，把"贪心个数 × 100 // 最优个数"当作放大 100 倍的比值 a = -1 b = -1 # TODO: 两个比值都不超过 200（也就是 2 倍）就输出「都没超」，否则「超了」 verdict = "超了" print(str(a) + "/" + str(b) + "/" + verdict)
本次输入：
输出：
👩🏫
AI
请登录后使用 AI 老师
×
登录后可获得解题思路、提示与错误分析。
去登录
关闭
🎉
恭喜你，回答正确！
系统判定：正确
我知道了
💬 题目评论
提交
全部评论
全部评论