对于《由对称性解2
问题:微软笔试题——http://hihocoder.com/problemset/problem/1108 最初想法,仍有待验证:http://bbs.bccn.net/thread-441260-1-1.html 最初想法是:只有成对出现的约束,1 2 0,才能够对问题进行限制,对问题结果照成影响,因此只需要考虑成对出现的约束
问题:微软笔试题——http://hihocoder.com/problemset/problem/1108
最初想法,仍有待验证:http://bbs.bccn.net/thread-441260-1-1.html
最初想法是:只有成对出现的约束,1 2 0,才能够对问题进行限制,对问题结果照成影响,因此只需要考虑成对出现的约束。对于成对出现的节点,在构图中有
1 2 1
无向边进行连接,然后检测最终构图中是否存在节点个数为奇数的环,从而得到最后的结果。
解答:http://blog.csdn.net/kk303/article/details/42869039
由对称性解2-sat问题:http://wenku.baidu.com/link?url=G8jqWFFet0uc164GJnXwyCtJRoi0DQH0U1aoDIRdI7sdSS7R7-h6iacr4cENA808XvkbUV7Atj3MZxTP_r4gksh_IwXV1Bn76YRRMTwSIWq
1.问题模型:
存在n组元素
A1 | A2 | A3 | ... | An |
~A1 | ~A2 | ~A3 |
... | ~An |
规定每组元素中能且仅能选择一个,同时给定m组约束(Ai,Aj),约束也可能是(Ai,~Aj)。一组约束中的两个元素相互冲突,不能同时被选择。
求解是否能在约束限制下,在n组元素中选择出n个元素。若能,进行选择。
2.解法:步骤(1):对每对约束(Ai,Aj)。因为存在关系选择 Ai 则必须选择 ~Aj ,而选择 Aj 则必须选择 ~Ai ,因此在构图( 图的节点个数为2n)时,对于(Ai,~Aj),(Aj,~Ai)添加有向边。
步骤(2):在构图中查找极大强连通分量。将强连通分量转化为节点。这个步骤叫做缩图。
步骤(3):查找是否存在(Ai,~Ai)处于同一个强连通分量中,如果存在,问题无解,程序终止。
步骤(4):根据拓扑排序找到一个可行解。
推荐阅读