[SHOI2001]小狗散步(最大匹配)

题目链接

题解

把人走的点当作左部节点,🐕走的当作右部
对于每个人走的节点,如果他与下一个节点的距离的两倍大于某个从当前节点走到右部节点+右部节点走到下一节点的距离,即可连边
输出方案的话,注意到如果右部节点被匹配,match[i]就是匹配它的左部节点,存起来输出即可

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注