首页 > 牛牛选路径
开通博客写题解
头像 沉默与剑
发表于 2021-12-10 22:09:06
牛牛选路径 约定：称度数为奇数的点为奇点，称度数为偶数的点为偶点。 贪心策略： 对于每一个连通块，考虑以下两种情况： 如果不存在奇点，则选择点权最小的点作为头尾连接一条路径。 存在奇点，则必然有偶数个奇点，只需要选出这些奇点之间的最优匹配， 而这个最优匹配就是：排序之后不断取最小值和最大值匹 展开全文
去ta的博客 赞 (5) 回复(2) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”