BZOJ 2199 && luguoP3007 [USACO11JAN]大陆议会The Continental Cowngress 2-sat

对板子有了更深刻的理解,只要2-sat存在,那么dfs函数求出的一个方案一定是一个合法解的子集。

BZOJ 1823 1823: [JSOI2010]满汉全席 2-sat

对这套2-sat板子又有了更深刻的理解。现在感觉kuangbin这套板子真的很妙,应该可以处理所有的2-sat问题。

POJ 3683 Priest John’s Busiest Day 2-sat

就是两个时间段必须选一个,依旧用的kuangbin的那套理论。现在我觉得这套理论可能只支持两个只能选一个情况。还在研究。

hdu 1814 Peaceful Commission 2-sat

观摩了下kuangbin大佬的板子。太简洁巧妙了!但是感觉似乎这个板子对于两个东西至少选一个不是通过建边保证,而是用了其他的方式,感觉也不不太通用,自己在多了解了解

POJ3678 Katu Puzzle 2-sat tarjan

if后面加了个;debug半小时,论如何提高智商,真是个永恒的话题。

i + n 表示i选1,i表示i选0,建图如下