暑假还以为2-sat就是求强连通分量呢
原来不仅如此啊
贴个链接。。。写的很好啊
http://www.cppblog.com/y346491470/articles/156782.html
比较明显的2-Sat问题，关键是要把所有情况考虑完全。用x表示该变量取0，x’表示取1，下面说下如何构图:
a and b == 1, 这种情况a和b必须取1，所以连边a->a', b->b'.
a and b == 0, 这种情况a和b不能同时为1，所以连边a'->b, b'->a.
a or b == 1, 这种情况a和b不能同时为0，所以连边a->b', b->a'.
a or b == 0, 这种情况a和b必须同时为0，所以连边a'->a, b'->b.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b', a'->b, b->a', b'->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a'->b', b'->a'.
构图后强连通缩点判断有无解即可。
首先第一个祼题：http://acm.hdu.edu.cn/showproblem.php?pid=3062
把没有矛盾的连边求targan就行
第二题：http://poj.org/problem?id=3678
这题做完之后还是不理解啊
最后就是这次长春赛的题了：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4879
有一点改变，求31次targan，就是每一位都求一次，一次不符合即NO了
唉。。。加油吧