P4782 【模板】2-SAT 问题

    • 1.4K通过
    • 4.3K提交
  • 题目提供者 happyZYM
  • 评测方式 云端评测
  • 标签 2-SAT 图论 强连通分量,缩点 O2优化 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    2-SAT 问题 模板

    题目描述

    有n个布尔变量$x_1$~$x_n$,另有m个需要满足的条件,每个条件的形式都是“$x_i$为true/false或$x_j$为true/false”。比如“$x_1$为真或$x_3$为假”、“$x_7$为假或$x_2$为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

    输入输出格式

    输入格式:

    第一行两个整数n和m,意义如体面所述。

    接下来m行每行4个整数 i a j b,表示“$x_i$为a或$x_j$为b”(a,b∈{0,1})

    输出格式:

    如无解,输出“IMPOSSIBLE”(不带引号); 否则输出"POSSIBLE"(不带引号),下 一行n个整数$x_1$~$x_n$($x_i$∈{0,1}),表示构造出的解。

    输入输出样例

    输入样例#1: 复制
    3 1
    1 1 3 0
    输出样例#1: 复制
    POSSIBLE
    0 0 0

    说明

    1<=n,m<=1e6 , 前3个点卡小错误,后面5个点卡效率,由于数据随机生成,可能会含有( 10 0 10 0)之类的坑,但按照最常规写法的写的标程没有出错,各个数据点卡什么的提示在标程里。

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。