TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2211
  • 题目
  • P2211【2-SAT】完美的选举
    限制 : 时间限制 : 5000 MS   空间限制 : 65536 KB
    问题描述

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

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

    输入格式

    有若干组测试数据,对于每组测试数据:
    只有一行,首先是两个整数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

    输出格式

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

    样例输入

    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

    样例输出

    1
    1
    0
    1

    提示

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


    来源  Southeastern European Regional Programming Contest 2008 POJ3905