bzoj 1728: [Usaco2006 Open]Two-Headed Cows 双头牛 二分+染色

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1728


最开始以为是2-sat

后来发现必须是连续一段

那这样就直接二分+染色就好了

如果两头牛同一侧的脑袋互相讨厌那就一定要翻转其中一个,所以就连一条1的边,否则连一条0的边

然后锁定左端点,二分右端点

dfs时,col[to]=col[now]^边权

当我们碰到一个访问过的但是颜色却和之前的不一样时,就代表不满足条件

 

发表评论