SAT算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了SAT算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2944字，纯文字阅读大概需要5分钟。
内容图文
今早用微云打的笔记...头大
我惊，这不是可爱的离散吗？！
建个有向图G，(Xi+Yi)加两边表示( ?Xi+Yi)(Xi+ ?Yi)
每个点（eg:A）加上 ?A
下图为:(A->B)·( ?B-> ?A)·( ?D->E)·( ?E->D)·( ?B->C)·( ?C-> B)·(C-> ?B)·(B-> ?C)·(C->D)·(D->C)·(C-> ?D)·( ?D-> ?C)
然后用Tarjan算法缩点
手热来了一发模板题https://www.luogu.org/problem/P4782
贴
1 #include <bits/stdc++.h>
2usingnamespace std;
3constint N=1e6+5;
4int n,m,a,b,fla,flb,cnt,head[N<<1];
5int dfn[N<<1],low[N<<1],vis[N<<1],col[N<<1],scnt,idx;
6 stack<int> st;
7struct edge{
8int to,next;
9 }e[N<<1];
10 inline void addedge(int a,int b)
11{
12 e[++cnt]={b,head[a]};
13 head[a]=cnt;
14}
15void tarjan(int u)
16{
17 dfn[u]=low[u]=++idx;vis[u]=1;
18 st.push(u);
19for(int i=head[u];i;i=e[i].next)
20 {
21if(!dfn[e[i].to]) tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);
22elseif(vis[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
23 }
24if(low[u]==dfn[u])
25 {
26 scnt++;int v=-1;
27while(v!=u)
28 {
29 v=st.top();st.pop();
30 col[v]=scnt,vis[v]=0;
31 }
32 }
33}
34int main()
35{
36for(scanf("%d%d",&n,&m);m--;){
37 scanf("%d%d%d%d",&a,&fla,&b,&flb);
38int aa=fla^1,bb=flb^1;
39 addedge(a+aa*n,b+flb*n);
40 addedge(b+bb*n,a+fla*n);
41 }
42for(int i=1;i<=2*n;i++)
43if(!dfn[i]) tarjan(i);
44for(int i=1;i<=n;i++)
45if(col[i]==col[n+i]) return puts("IMPOSSIBLE")&0;
46 puts("POSSIBLE");
47for(int i=1;i<=n;i++) printf("%d%c",col[i]>col[n+i],i==n?‘\n‘:‘‘);
48 }
然后又很智障得磕了http://acm.hdu.edu.cn/showproblem.php?pid=3062
因为初始化和下标问题还WA了半天，就简单YES、NO的我都能PE，自闭半小时
贴
1 #include <bits/stdc++.h>
2usingnamespace std;
3constint N=1005;
4int n,m,a,b,fla,flb,cnt,scnt,idx,flag;
5int head[N<<1],dfn[N<<1],low[N<<1],vis[N<<1],col[N<<1];
6 stack<int> st;
7struct edge{
8int to,next;
9 }e[N*N];
10void init()
11{
12 memset(head,-1,sizeof(head));
13 memset(dfn,0,sizeof(dfn));
14 memset(vis,0,sizeof(vis));
15 memset(low,0,sizeof(low));
16 cnt=idx=scnt=flag=0;
17}
18 inline void addedge(int a,int b)
19{
20 e[cnt]={b,head[a]};
21 head[a]=cnt++;
22}
23void tarjan(int u)
24{
25 dfn[u]=low[u]=++idx;vis[u]=1;
26 st.push(u);
27for(int i=head[u];i!=-1;i=e[i].next)
28 {
29if(!dfn[e[i].to]) tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);
30elseif(vis[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
31 }
32if(low[u]==dfn[u])
33 {
34 scnt++;
35int v=-1;
36while(v!=u)
37 {
38 v=st.top();st.pop();
39 col[v]=scnt,vis[v]=0;
40 }
41 }
42}
43int main()
44{
45while(~scanf("%d",&n))
46 {
47 scanf("%d",&m);
48 init();
49while(m--)
50 {
51 scanf("%d%d%d%d",&a,&b,&fla,&flb);
52 addedge((a<<1)+fla,((b<<1)+flb)^1);
53 addedge((b<<1)+flb,((a<<1)+fla)^1);
54 }
55for(int i=0;i<2*n;i++)
56if(!dfn[i]) tarjan(i);
57for(int i=0;i<2*n;i+=2)
58if(col[i]==col[i^1]){puts("NO");flag=1;break;}
59if(!flag) puts("YES");
60 }
61 }
原文：https://www.cnblogs.com/Aaaamber/p/11562029.html
内容总结
以上是互联网集市为您收集整理的SAT算法全部内容，希望文章能够帮你解决SAT算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】