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

等你来战

查看全部