更多文章可以在本人的个人小站:https://kaiserwilheim.github.io 查看。
转载请注明出处。
2-SAT问题的名字可以拆成两部分:2和SAT。
SAT是Satisfiability【可满足性】的简称。
解释一下,就是,我们有若干个需要赋值的布尔变量,要求对这些变量进行赋值,使得这些变量的值满足一组布尔方程。
举个例子:
宝硕需要讲解一个题目,他需要就着代码讲题,所以代码需要让每一个人看懂,并尽量满足每一个人的代码习惯。
听的人有三个:KaiserWilheim、Johnsonloy、JeffZhao。现在他们提出了一些要求,如下:
#define int long long
( ¬ b \neg b ¬b)#define int long long
( b b b)#define int long long
( ¬ b \neg b ¬b)我们可以将三种条件分别设为 a a a, b b b, c c c,变量前加 ¬ \neg ¬ 表示对当前要求表示否定。
那么上述要求可以变为 ( a ∨ ¬ b ∨ c ) ∧ ( a ∨ b ∨ c ) ∧ ( ¬ a ∨ ¬ b ∨ ¬ c ) (a \lor \neg b \lor c)\land(a \lor b \lor c)\land(\neg a \lor \neg b \lor \neg c) (a∨¬b∨c)∧(a∨b∨c)∧(¬a∨¬b∨¬c)。其中 ∨ \lor ∨ 表示或, ∧ \land ∧ 表示与。
现在我们需要为 a b c abc abc 三个变量赋值,满足三个人的要求。
怎么处理呢?
暴力。
因为SAT问题已经被证明为了**NPC(NP完全)**问题,只能暴力做。
那么2-SAT又是一种什么东西?
为什么我们需要把2-SAT单独拎出来?
2-SAT,就是每一个同学只有两个条件。
上面的问题就可以叫做3-SAT。
假如说Wilheim和Johnson一致决定将Jeff放在火刑架上使得Jeff放弃了大括号不换行,那么我们的问题就剩下了两个,要求就变为了 ( a ∨ ¬ b ) ∧ ( a ∨ b ) ∧ ( ¬ a ∨ ¬ b ) (a \lor \neg b)\land(a \lor b)\land(\neg a \lor \neg b) (a∨¬b)∧(a∨b)∧(¬a∨¬b)。
然后,宝硕就决定按照使用bits库和不使用#define int long long
来作为讲题用的代码风格。
我们怎么求解2-SAT问题呢?
使用强连通分量。
我们将每一个变量拆成两个点,记为 x x x 与 ¬ x \neg x ¬x。
对于每一个同学的要求 ( a ∨ b ) (a \lor b) (a∨b),我们尝试将其转化为 ¬ a → b ∧ ¬ b → a \neg a \to b \land \neg b \to a ¬a→b∧¬b→a。
因为我们需要使 a a a 和 b b b 中间至少有一个是真,那么我们一旦 a a a 为假那么 b b b 就一定为真,反之同理。
那么我们这样建图:
式子 | 建图 |
---|---|
a ∨ b a \lor b a∨b | ¬ a → b ∧ ¬ b → a \neg a \to b \land \neg b \to a ¬a→b∧¬b→a |
¬ a ∨ b \neg a \lor b ¬a∨b | a → b ∧ ¬ b → ¬ a a \to b \land \neg b \to \neg a a→b∧¬b→¬a |
a ∨ ¬ b a \lor \neg b a∨¬b | ¬ a → ¬ b ∧ b → a \neg a \to \neg b \land b \to a ¬a→¬b∧b→a |
¬ a ∨ ¬ b \neg a \lor \neg b ¬a∨¬b | a → ¬ b ∧ b → ¬ a a \to \neg b \land b \to \neg a a→¬b∧b→¬a |
上面的图就变成了这个样子:
我们可以发现, a a a 和 ¬ b \neg b ¬b 在同一强连通分量内,同时 ¬ a \neg a ¬a 和 b b b 也在同一强连通分量内。
在同一强连通分量内就代表着知道了一个数的值之后就可以推出其他所有变量的值,所以我们给同一个强连通分量内的变量取值是相同的。
那么我们就给 a a a 和 ¬ b \neg b ¬b 都取真,那么就意味着 a = 1 , b = 0 a=1,b=0 a=1,b=0。
当然我们也可以给 ¬ a \neg a ¬a 和 b b b 取真,也是一个可行解。
习惯上,我们给缩点后的图排一个拓扑序,当 x x x 所在强连通分量的拓扑序在 ¬ x \neg x ¬x 所在的强连通分量的拓扑序之后的话我们就给 x x x 取真。
那么我们什么时候才没有可行解呢?
当且仅当 x x x 与 ¬ x \neg x ¬x 在同一个强连通分量里面的时候。
这样 x x x 需要同时取真和假两个值,整个方程组就无解了。
用tarjan来求强联通分量就可以了。
tarjan同时还给缩点后的图排了一下序,就不需要我们再排拓扑序了。
洛谷例题:https://www.luogu.com.cn/problem/P4782
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2000010, M = 4000010;
int n, m;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfn[N], low[N], cnt;
int sta[N], tt;
bool vis[N];
int scc[N], sc, sz[N];
void tarjan(int p)
{
low[p] = dfn[p] = ++cnt;
sta[++tt] = p, vis[p] = true;
for(int i = h[p]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[p] = min(low[p], low[j]);
}
else if(vis[j])
{
low[p] = min(low[p], dfn[j]);
}
}
if(dfn[p] == low[p])
{
++sc;
while(sta[tt] != p)
{
scc[sta[tt]] = sc;
sz[sc]++;
vis[sta[tt]] = false;
tt--;
}
scc[sta[tt]] = sc;
sz[sc]++;
vis[sta[tt]] = false;
tt--;
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
int x, y, a, b;
scanf("%d%d%d%d", &x, &a, &y, &b);
add(x + !a * n, y + b * n);
add(y + !b * n, x + a * n);
}
for(int i = 1; i <= 2 * n; i++)
if(!dfn[i])tarjan(i);
for(int i = 1; i <= n; i++)
{
if(scc[i] == scc[i + n])
{
puts("IMPOSSIBLE");
return 0;
}
}
puts("POSSIBLE");
for(int i = 1; i <= n; i++)
if(scc[i] < scc[i + n])printf("0 ");
else printf("1 ");
return 0;
}
文章浏览阅读37次。rm -rf mydir /* 删除mydir目录 */ cd mydir /* 进入mydir目录 */ cd – /* 回上一级目录 */ cd ~ /* 回根目录 */ mv tools tool /* 把tools目录改名为tool */ ln -s tool bac/* 给tool目录创建名为bac的符号链接,最熟悉的应该就是FTP中www链接到public_html目录了...
文章浏览阅读1.2k次。以上是30个常用的思科设备巡检命令,用于获取设备的各种配置和状态信息。在网络设备的日常运维和故障排查中,这些命令可以帮助管理员快速了解设备的状态、配置和性能情况,以便及时发现和解决潜在的问题。今天给大家带来的是30个思科设备巡检的命令,每个命令都有解释,希望对每位网络工程师有所帮助!你好,这里是网络技术联盟站。_思科ac巡检命令
文章浏览阅读2w次。mac电脑触控板快速选择前提:在截图或者选择的时候,点击触控板在拖动会很麻烦,mac提供一个三指拖移的功能,能够用三指快速拖移,这样就变成四指切换。步骤左上角,点击苹果logo,选择系统偏好设置点击辅助功能,选择“鼠标与触控板”点击“触控板选项”,勾选启动拖移,选择“三指拖移”,选择“好”就设置完毕啦。这样,就可以一指滑动,轻触点击;二指滑动三指拖移四指切换面板棒呆..._mac trackpad 两指移动
文章浏览阅读2.2k次。文章目录1 图片被划分为CTU2 图片被划分为SubPicture、Slice、Tile2.1 Tile、SLice、SubPicture的概念2.2 光栅扫描分区模式2.3 矩形分区模式3 CTU以树形继续向下划分3.1 HEVC的划分方式3.2 VVC的划分方式3.3 编解码方式3.4 示例3.5 高层参数及限制3.6 帧内的色度独立划分4 CU在图片边缘的划分5 CU冗余划分的限制6 虚拟管..._h.266 ctb
文章浏览阅读1.5k次。从零开始搭建自己的vue组件库——01创建引言项目创建修改目录结构添加第一个组件以及样式文件夹引言因工作需要,要打造一套属于自己团队的组件库,本人也是第一次接到这种任务,虽然不着急,但是之前从来没做过,因此特意再此记录下过程,也希望自己能坚持下去,当然,过程中少不了查阅各种资料,也会再次记录下各种各样的问题,本组件库的开发基于vue2.0,主要用于pc端,会参考element-ui进行开发项目创建首先第一步是要创建一个vue工程vue create xxxx创建具体流程在这里不再详细说明,创建完_vue构建自己的组件库
文章浏览阅读1.3k次。神经网络在优化中的应用:万能的模型+误差修正函数“,每次根据训练得到的结果与预想结果进行误差分析,进而修改权值和阈值,一步一步得到能输出和预想结果一致的模型。举一个例子:比如某厂商生产一种产品,投放到市场之后得到了消费者的反馈,根据消费者的反馈,厂商对产品进一步升级,优化,从而生产出让消费者更满意的产品。这就是BP神经网络的核心。BP神经网络是一种按误差反向传播(简称误差反传)训练的多层前馈网络,其算法称为BP算法,它的基本思想是梯度下降法,利用梯度搜索技术,以期使网络的实际输出值和期望输出值的误差均方
文章浏览阅读2.3k次,点赞2次,收藏2次。zhuanzai1.密钥长度rsa算法初始化的时候一般要填入密钥长度,在96-1024bits间(1)为啥下限是96bits(12bytes)?因为加密1byte的明文,需要至少1+11=12bytes的密钥(不懂?看下面的明文长度),低于下限96bits时,一个byte都加密不了,当然没意义啦(2)为啥上限是1024(128bytes)?这是算法本身决定的...当然如果某天网上出_rsa2048原文长度限制
文章浏览阅读1.7k次。llua的源码和php后台源码,功能有,卡密系统,远程公告,远程更新,文件系统,网站默认账号 admin 123456使用方法:wwrgu.lanzouq.com/irLiC061rkhc_网络验证源码
文章浏览阅读3.7k次,点赞2次,收藏14次。目录写在前面SM规范简述安全管理器加密工具配对流程安全属性IO功能加密密钥大小配对算法低功耗蓝牙安全密钥和值的定义分发密钥的生成密钥分配安全管理器会话协议介绍命令格式写在前面安全规范协议,主要是描述LE控制器设备配对、认证、加密等过程进行规定,同时也对相关算法进行了说明。低功耗蓝牙的安全管理经历了几个阶段,LE传统配对方式和安全连接。这篇协议基本上是参考蓝牙核心协v5.0议进行的翻译,并且只选取了我认为重要的部分,如果需要深入详_smp协议
文章浏览阅读98次。计算在-10.8到5.9之间,绝对值大于6或者小于2.1的整数有多少个?编写Demo04MathPractise.java类package com.iflytek.day08.demo04;/*题目:计算在-10.8到5.9之间,绝对值大于6或者小于2.1的整数有多少个?分析:1. 既然已经确定了范围,for循环2. 起点位置-10.8应该转换成为-10,两种办法: 2.1 可以使用Math.ceil方法,向上(向正方向)取整 2.2 强转成为int,自动舍弃所有小数位3_java math计算在 -10.8 到 5.9 之间,绝对值大于 6 或者小于 2.1 的整数有多少个?
文章浏览阅读1.7k次。C++使用随机数_c++suijizhongzi
文章浏览阅读793次。参考地址:http://blog.csdn.net/jj120522/article/details/8075249