保存帖子
发现
索引
热门
陶片放逐
关于
建议升蓝
板块
AT_abc383_e [ABC383E] Sum of Max Matching
楼主
litjohn
当前回复
24
已保存回复
25
发布时间
2024/12/17 18:34
上次更新
2024/12/28 09:24:42
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
建议升蓝
litjohn
楼主
2024/12/17 18:34
本题的主流做法需要证明三个命题:
kruskal 最小生成树的正确性
两点间最大边权最小的路径在最小生成树上
贪心地将每个 a 中元素匹配到最“近”的 b 中元素的正确性
仅是前两个问题就是
货车运输
,而且本题还有第三个命题的证明和使用并查集做贪心的部分,难度与货车运输接近,建议升蓝。
2024/12/17 18:34
加载中...