2-SAT——CodeForces #400 D

    xiaoxiao2021-03-25  91

    题目链接: http://codeforces.com/contest/776/problem/D

    题意: 给出N扇门的状态:开或者关,给出M个开关,每个开关控制任意数量门,按下开关,这些门的状态同时改变,但是每个门都恰好被2个开关控制,求能否将所有门都打开

    分析:

    对立关系:开关 用或者不用 矛盾关系: 如果某扇门是关闭状态,那么与它相关的两个开关a和b,就只能选择一个使用,不能两个不用:矛盾关系(~a,~b), 也不能两个都用:矛盾关系(a,b) 如果某扇门是打开状态,那么与它相关的两个开关a和b,就只能都使用,或者都不使用,不能只使用一个:矛盾关系(a,~b)&&(b,~a);
    转载请注明原文地址: https://ju.6miu.com/read-13865.html

    最新回复(0)