TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2211
  • Problem
  • P2211【2-SAT】完美的选举
    Limits : Time Limit : 5000 MS   Memory Limit : 65536 KB
    Description

    在某个国家,有n(编号1到n)个议员候选人参加选举。有一项民意调查的问题是“这n个候选人中只能选两个,哪种选举结果你会满意?”,有M份调查结果送到你的桌子上。调查结果中,有人选的两个人是不同的,也可能有人选的两个人是同一个人。

    现在有你根据这M份调查表来决定是否会有一个确切的选举结果(全都没被选中、全都被选中了、只有部分被选中,这些都是确切的选举结果),如果有确切的选角结果,输出1,否则输出0。

    Input Format

    有若干组测试数据,对于每组测试数据:
    只有一行,首先是两个整数N和M(1≤N≤1000 和 1≤M≤1000000),接着是M对“±i ±j”表示M张调查表(1≤i,j≤N).
    每张调查表可能是如下情况:


    问题答案: 表示方式
    1.i和j中至少一人当选,我就很满意 +i +j
    2.i和j中至少一人不当选,我就很满意 -i -j
    3.i当选,或者j不当选,或者i当选同时j不当选,我就很满意 +i -j
    4.i不当选,或者j当选,或者i不当选同时j当选,我就很满意 -i +j

    Output Format

    对于每组测试数据,有确定的选举结果,输出1,否则输出0

    Sample Input

    3 3  +1 +2  -1 +2  -1 -3 
    2 3  -1 +2  -1 -2  +1 -2 
    2 4  -1 +2  -1 -2  +1 -2  +1 +2 
    2 8  +1 +2  +2 +1  +1 -2  +1 -2  -2 +1  -1 +1  -2 -2  +1 -1

    Sample Output

    1
    1
    0
    1

    Hint

    第3组样例说明:
    根据 -1 +2 和 -1 -2 ,说明1不能当选,
    但是根据+1 -2 和 +1 +2 ,说明1必须当选,矛盾,所以无法得到确切的选举结果


    Source  Southeastern European Regional Programming Contest 2008 POJ3905