轻松的编程学习
首页
题库
学习路径
在线商城
能力地图
下载应用
登录 / 注册
菜单
自己写：2-近似的顶点覆盖
👁️ 0 人浏览
💬 0 人评论
❤️ 添加收藏
补全贪心：
挨条边看，两头都没被盖住就把两头一起收下
。
提交你的答案
请登录后提交答案。
去登录
← ⚠️ 换一张图，比值正好顶到 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: # TODO: 这条边两头都还没被盖住，就把两头都收进 cover 和 used pass 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) print(str(len(greedy_vc(E))) + "/" + str(len(opt_vc(E, V))))
本次输入：
输出：
👩🏫
AI
请登录后使用 AI 老师
×
登录后可获得解题思路、提示与错误分析。
去登录
关闭
🎉
恭喜你，回答正确！
系统判定：正确
我知道了
💬 题目评论
提交
全部评论
全部评论