首页 > 编程语言 > 详细

2-SAT算法

时间:2019-08-18 19:49:42      阅读:82      评论:0      收藏:0      [点我收藏+]

例题:

https://www.luogu.org/problem/P4782

算法:

算法所求问题:

这个算法主要是求有n个人,每个有m个要求,要求只可能是1或0的情况(及是或不是 || 要或不要......),且每个要求只需满足其一即可,求是否有可行的分配方案(当然,也可以求出那个可行的分配方案)

算法前置知识:

Tarjan求强连通分量,拓扑序

算法主要思路:

首先声明一下:a --> b(a向b连一条边)表示如果慢足a这个条件,就必须满足b这个条件;a本身表示选a,a + n表示不选a。开始说思路:如果有一个要求是选a或者不选b,那么我们可以从a + n向b + n连一条边(如果不选a了,就必须不选b,否则就不满足这个要求了),然后我们也从b向a连一条边(如果选b了,就必须选a,否则就不满足要求了)

2-SAT算法

原文:https://www.cnblogs.com/qqq1112/p/11373590.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!