题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3622
思路:二分是容易想到的,由于题目中有明显的矛盾关系,因此可以用2-sat来验证其可行性。关键是如何建图:对于每两对炸弹的(u,u')和(v,v'),如果u,vi的距离小于2*mid,则连边u->v',v->u‘。然后强连通判断可行性。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3622
思路:二分是容易想到的,由于题目中有明显的矛盾关系,因此可以用2-sat来验证其可行性。关键是如何建图:对于每两对炸弹的(u,u')和(v,v'),如果u,vi的距离小于2*mid,则连边u->v',v->u‘。然后强连通判断可行性。