2-sat
分类:
IT文章
•
2022-04-04 12:38:31
建议初学者先参考：伍昱的《由对称性解2-sat问题》 - 03年IOI国家集训队论文ppt
还有参考http://www.cnblogs.com/silver-bullet/archive/2013/02/18/2915097.html
下面的算法一指暴力枚举，算法二指缩点拓扑。
HDU 1814 Peaceful Commission
题意：2n个人，2i-1 和 2i 选且仅选1人。有m对不和人，不和的两人不能同时被选。输出最小字典序的合法方案。
题解：ppt里的经典例题。由于需要最小字典序，需要暴力2-sat。若i和j不和，显然选i则只能选j'，选j则只能选i'。（这里注意，选i'（或j'）可以选j(i)也可以选j'(i')）
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6
7 #define N 16010
8 #define M 40010
9 struct Edge{
10 int u,v,nxt;
11 }e[M];
12 int head[N],m;
13 void init(){ m=0; memset(head,-1,sizeof(head)); }
14 void addedge(int u,int v){
15 e[m].u=u, e[m].v=v, e[m].nxt=head[u];
16 head[u]=m++;
17 }
18 int c[N];
19 int que[N],tl;// temp
20 bool dfs(int u){
21 if(c[u]==1)return true;
22 if(c[u]==0)return false;
23 c[u]=1;
24 c[u^1]=0;
25 que[tl++]=u;
26 for(int i=head[u]; i!=-1; i=e[i].nxt)
27 if(dfs(e[i].v)==false) return false;
28 return true;
29 }
30 bool solve(int n){
31 memset(c,-1,sizeof(c));
32 for(int i=0; i<2*n; i+=2){
33 if(c[i] != -1) continue;
34 tl = 0;
35 if(!dfs(i)){
36 for(int j=0;j<tl;++j)
37 c[que[j]] = c[que[j]^1] = -1;
38 if(!dfs(i+1)) return false;
39 }
40 }
41 return true;
42 }
43 int main(){
44 int n,m;
45 while(~scanf("%d%d",&n,&m)){
46 init();
47 for(int i=1;i<=m;i++){
48 int a,b;
49 scanf("%d%d",&a,&b);
50 --a,--b;
51 addedge(a,b^1);
52 addedge(b,a^1);
53 }
54 if(solve(n)){
55 for(int i=0;i<2*n;i++){
56 if(c[i]==1) printf("%d
",i+1);
57 }
58 }
59 else puts("NIE");
60 }
61 return 0;
62 }
HDU 1814 算法一
POJ 3207 Ikki's Story IV - Panda's Trick
题意：圆上有n个点，m条边，边的端点是那n个点中的2个点。边可以在圆内或圆外，输入保证每个点最多只是一条边的端点。问边是否相交。
题解：圆内和圆外2种情况，可以把边当做2-sat中的点。若2条圆内边相交，则这2条边的圆外边必定相交。即，若i与j相交，则选i只能选j'，选j只能选i'，选i'只能选j，选j'只能选i。注意(a,b)和(c,d)相交的判断条件是(a-c)*(a-d)*(b-c)*(b-d)<0.
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6
7 #define N 1010
8 #define M (1010*2010)
9 struct Edge{
10 int u,v,nxt;
11 }e[M];
12 int head[N],m;
13 void init(){ m=0; memset(head,-1,sizeof(head)); }
14 void addedge(int u,int v){
15 e[m].u=u, e[m].v=v, e[m].nxt=head[u];
16 head[u]=m++;
17 }
18 int c[N];
19 int que[N],tl;// temp
20 bool dfs(int u){
21 if(c[u]==1)return true;
22 if(c[u]==0)return false;
23 c[u]=1;
24 c[u^1]=0;
25 que[tl++]=u;
26 for(int i=head[u]; i!=-1; i=e[i].nxt)
27 if(dfs(e[i].v)==false) return false;
28 return true;
29 }
30 bool solve(int n){
31 memset(c,-1,sizeof(c));
32 for(int i=0; i<2*n; i+=2){
33 if(c[i] != -1) continue;
34 tl = 0;
35 if(!dfs(i)){
36 for(int j=0;j<tl;++j)
37 c[que[j]] = c[que[j]^1] = -1;
38 if(!dfs(i+1)) return false;
39 }
40 }
41 return true;
42 }
43 int main(){
44 int n,m;
45 int uv[510][2];
46 while(~scanf("%d%d",&n,&m)){
47 init();
48 for(int i=1;i<=m;i++) scanf("%d%d",&uv[i][0],&uv[i][1]);
49 for(int i=1;i<=m;++i){
50 for(int j=i+1;j<=m;++j){
51 int a=uv[i][0],b=uv[i][1],c=uv[j][0],d=uv[j][1];
52 if(1ll*(a-c)*(a-d)*(b-c)*(b-d)<0){
53 int u=i*2-2,v=j*2-2;
54 addedge(u,v^1);
55 addedge(v^1,u);
56 addedge(v,u^1);
57 addedge(u^1,v);
58 }
59 }
60 }
61 if(solve(m)) puts("panda is telling the truth...");
62 else puts("the evil panda is lying again");
63 }
64 return 0;
65 }
POJ 3207 算法一
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <queue>
6 using namespace std;
7
8 #define maxn 1010
9 vector<int>e[maxn],ee[maxn];
10 int dfn[maxn],low[maxn],id,cnt;
11 bool ins[maxn];
12 int st[maxn],top;
13 int belong[maxn];
14 void strongconnect(int x,int fa){
15 dfn[x]=low[x]=++id;
16 st[top++]=x;
17 ins[x] = true;
18 for(int i=e[x].size()-1;i>=0;--i){
19 int v = e[x][i];
20 if(!dfn[v]){
21 strongconnect(v,x);
22 low[x] = min(low[x],low[v]);
23 //if(low[v]>=dfn[u]) cutp[u] = true;
24 //if(low[v]>dfn[u]) cute[u][v] = true;
25 }
26 else if(ins[v]) low[x] = min(low[x],dfn[v]);
27 }
28 if(dfn[x]==low[x]){
29 int u=-1;
30 while(u!=x){
31 u = st[--top];
32 ins[u]=false;
33 belong[u]=cnt;
34 }
35 ++cnt;
36 }
37 }
38 void tarjan(int n){
39 id=cnt=top=0;
40 memset(dfn,0,sizeof(dfn));
41 memset(low,0,sizeof(low));
42 memset(ins,0,sizeof(ins));
43 for(int i=0;i<n;++i)
44 if(!dfn[i]) strongconnect(i,-1);
45 }
46 bool solve(int n){
47 tarjan(n);
48 bool flag = true;
49 for(int i=0;i<n;i+=2)
50 if(belong[i]==belong[i^1]) flag = false;
51 return flag;
52 }
53 int main(){
54 int n,m;
55 int uv[510][2];
56 while(~scanf("%d%d",&n,&m)){
57 for(int i=0;i<=2*m;++i) e[i].clear(),ee[i].clear();
58 for(int i=1;i<=m;i++) scanf("%d%d",&uv[i][0],&uv[i][1]);
59 for(int i=1;i<=m;++i){
60 for(int j=i+1;j<=m;++j){
61 int a=uv[i][0],b=uv[i][1],c=uv[j][0],d=uv[j][1];
62 if(1ll*(a-c)*(a-d)*(b-c)*(b-d)<0){
63 int u=i*2-2,v=j*2-2;
64 e[u].push_back(v^1);
65 e[v^1].push_back(u);
66 e[v].push_back(u^1);
67 e[u^1].push_back(v);
68 }
69 }
70 }
71 if(solve(2*m)) puts("panda is telling the truth...");
72 else puts("the evil panda is lying again");
73 }
74 return 0;
75 }
POJ 3207 算法二
HDU 3622 Bomb Game
题意：2n个同半径圆，2i-1和2i 选且仅选1个。输出最大半径使得所有圆之间互相不想交。
题解：若i和j相交，显然选i则只能选j'，选j则只能选i'。二分答案。
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 using namespace std;
6
7 #define N 210
8 #define M (210*210)
9 #define eps 1e-8
10 struct Edge{
11 int u,v,nxt;
12 }e[M];
13 int head[N],m;
14 void init(){ m=0; memset(head,-1,sizeof(head)); }
15 void addedge(int u,int v){
16 e[m].u=u, e[m].v=v, e[m].nxt=head[u];
17 head[u]=m++;
18 }
19 int c[N];
20 int que[N],tl;// temp
21 bool dfs(int u){
22 if(c[u]==1)return true;
23 if(c[u]==0)return false;
24 c[u]=1;
25 c[u^1]=0;
26 que[tl++]=u;
27 for(int i=head[u]; i!=-1; i=e[i].nxt)
28 if(dfs(e[i].v)==false) return false;
29 return true;
30 }
31 bool solve(int n){
32 memset(c,-1,sizeof(c));
33 for(int i=0; i<2*n; i+=2){
34 if(c[i] != -1) continue;
35 tl = 0;
36 if(!dfs(i)){
37 for(int j=0;j<tl;++j)
38 c[que[j]] = c[que[j]^1] = -1;
39 if(!dfs(i+1)) return false;
40 }
41 }
42 return true;
43 }
44 struct Point{
45 double x,y;
46 }pnt[210];
47 double dis2(Point a,Point b){
48 double dx = a.x-b.x, dy = a.y-b.y;
49 return dx*dx+dy*dy;
50 }
51 bool jud(int n,double R){
52 init();
53 for(int i=0;i<2*n;++i){
54 for(int j=i+1;j<2*n;++j){
55 if(dis2(pnt[i],pnt[j])<4*R*R-eps && i!=(j^1)){
56 addedge(i,j^1);
57 addedge(j,i^1);
58 }
59 }
60 }
61 return solve(n);
62 }
63 int main(){
64 int n;
65 while(~scanf("%d",&n)){
66 for(int i=0;i<n;++i) scanf("%lf%lf%lf%lf",&pnt[i<<1].x,&pnt[i<<1].y,&pnt[i<<1|1].x,&pnt[i<<1|1].y);
67 double l=0,r=1e9;
68 while(l<r-eps){
69 double mid = (l+r)/2;
70 if(jud(n,mid)) l=mid;
71 else r=mid;
72 }
73 printf("%.2lf
",l);
74 }
75 return 0;
76 }
HDU 3622 算法一
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <queue>
6 using namespace std;
7
8 #define maxn 210
9 #define eps 1e-8
10 vector<int>e[maxn],ee[maxn];
11 int dfn[maxn],low[maxn],id,cnt;
12 bool ins[maxn];
13 int st[maxn],top;
14 int belong[maxn];
15 void strongconnect(int x,int fa){
16 dfn[x]=low[x]=++id;
17 st[top++]=x;
18 ins[x] = true;
19 for(int i=e[x].size()-1;i>=0;--i){
20 int v = e[x][i];
21 if(!dfn[v]){
22 strongconnect(v,x);
23 low[x] = min(low[x],low[v]);
24 //if(low[v]>=dfn[u]) cutp[u] = true;
25 //if(low[v]>dfn[u]) cute[u][v] = true;
26 }
27 else if(ins[v]) low[x] = min(low[x],dfn[v]);
28 }
29 if(dfn[x]==low[x]){
30 int u=-1;
31 while(u!=x){
32 u = st[--top];
33 ins[u]=false;
34 belong[u]=cnt;
35 }
36 ++cnt;
37 }
38 }
39 void tarjan(int n){
40 id=cnt=top=0;
41 memset(dfn,0,sizeof(dfn));
42 memset(low,0,sizeof(low));
43 memset(ins,0,sizeof(ins));
44 for(int i=0;i<n;++i)
45 if(!dfn[i]) strongconnect(i,-1);
46 }
47 bool solve(int n){
48 tarjan(n);
49 for(int i=0;i<n;i+=2)
50 if(belong[i]==belong[i^1]) return false;
51 return true;
52 }
53 struct Point{
54 double x,y;
55 }pnt[210];
56 double dis2(Point a,Point b){
57 double dx = a.x-b.x, dy = a.y-b.y;
58 return dx*dx+dy*dy;
59 }
60 bool jud(int n,double R){
61 for(int i=0;i<=2*n;++i) e[i].clear();
62 for(int i=0;i<2*n;++i){
63 for(int j=i+1;j<2*n;++j){
64 if(dis2(pnt[i],pnt[j])<4*R*R-eps && i!=(j^1)){
65 e[i].push_back(j^1);
66 e[j].push_back(i^1);
67 }
68 }
69 }
70 return solve(2*n);
71 }
72 int main(){
73 int n;
74 while(~scanf("%d",&n)){
75 for(int i=0;i<n;++i) scanf("%lf%lf%lf%lf",&pnt[i<<1].x,&pnt[i<<1].y,&pnt[i<<1|1].x,&pnt[i<<1|1].y);
76 double l=0,r=1e9;
77 while(l<r-eps){
78 double mid = (l+r)/2;
79 if(jud(n,mid)) l=mid;
80 else r=mid;
81 }
82 printf("%.2lf
",l);
83 }
84 return 0;
85 }
HDU 3622 算法二
题意：n个婚礼时间段（S[i],T[i]），每个婚礼有一个“特别庆祝祝福”的时长D[i]，“特别庆祝祝福”只会在(S[i],S[i]+D[i])或(T[i]-D[i],T[i])。问如何安排可不错过所有婚礼的“特别庆祝祝福”。
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <queue>
6 using namespace std;
7
8 #define maxn 2010
9 #define maxm (2010*2010)
10 struct Edge{
11 int v,nxt;
12 }e[maxm],ee[maxm];
13 int head[maxn],hh[maxn];
14 int em,eem;
15 void init(){em=0,eem=0;memset(head,-1,sizeof(head));memset(hh,-1,sizeof(hh));}
16 void addedge(int u,int v){
17 e[em].v=v,e[em].nxt=head[u];
18 head[u]=em++;
19 }
20 void addedge2(int u,int v){
21 ee[eem].v=v,ee[eem].nxt=hh[u];
22 hh[u]=eem++;
23 }
24 int dfn[maxn],low[maxn],id,cnt;
25 bool ins[maxn];
26 int st[maxn],top;
27 int belong[maxn];
28 int nn[maxn];
29 void strongconnect(int x,int fa){
30 dfn[x]=low[x]=++id;
31 st[top++]=x;
32 ins[x] = true;
33 for(int i=head[x];i!=-1;i=e[i].nxt){
34 int v = e[i].v;
35 if(!dfn[v]){
36 strongconnect(v,x);
37 low[x] = min(low[x],low[v]);
38 //if(low[v]>=dfn[u]) cutp[u] = true;
39 //if(low[v]>dfn[u]) cute[u][v] = true;
40 }
41 else if(ins[v]) low[x] = min(low[x],dfn[v]);
42 }
43 if(dfn[x]==low[x]){
44 int u=-1;
45 nn[cnt]=0;
46 while(u!=x){
47 u = st[--top];
48 ins[u]=false;
49 belong[u]=cnt;
50 nn[cnt]++;
51 }
52 ++cnt;
53 }
54 }
55 void tarjan(int n){
56 id=cnt=top=0;
57 memset(dfn,0,sizeof(dfn));
58 memset(low,0,sizeof(low));
59 memset(ins,0,sizeof(ins));
60 for(int i=0;i<n;++i)
61 if(!dfn[i]) strongconnect(i,-1);
62 }
63 bool vise[maxn][maxn];
64 bool solve(int n){
65 tarjan(n);
66 for(int i=0;i<n;i+=2)
67 if(belong[i]==belong[i^1]) return false;
68 int in[maxn];
69 memset(in,0,sizeof(in));
70 memset(vise,false,sizeof(vise));
71 for(int i=0;i<n;++i){
72 for(int j=head[i];j!=-1;j=e[j].nxt){
73 int u = belong[i], v = belong[e[j].v];
74 if(u==v || vise[v][u]) continue;
75 addedge2(v,u);
76 vise[v][u]=true;
77 ++in[u];
78 }
79 }
80 queue<int>que;
81 memset(ins,false,sizeof(ins));
82 int idx=0;
83 for(int i=0;i<cnt;++i) if(in[i]==0) que.push(i), dfn[i]=idx++;
84 while(!que.empty()){
85 int u = que.front(); que.pop();
86 for(int i=hh[u];i!=-1;i=ee[i].nxt){
87 int v = ee[i].v;
88 if(--in[v]==0){
89 que.push(v);
90 dfn[v]=idx++;
91 }
92 }
93 }
94 return true;
95 }
96 int main(){
97 int n;
98 int times[2010];
99 int cost[1010];
100 while(~scanf("%d",&n)){
101 for(int i=0;i<n;++i){
102 int t1,t2,t3,t4,t5;
103 scanf("%d:%d%d:%d%d",&t1,&t2,&t3,&t4,&t5);
104 times[i<<1]=t1*60+t2, times[i<<1|1]=t3*60+t4-t5;
105 cost[i] = t5;
106 }
107 init();
108 for(int i=0;i<2*n;++i){
109 for(int j=i+1;j<2*n;++j){
110 if(i==(j^1)) continue;
111 int a,b,c,d;
112 a = times[i], b = times[i]+cost[i/2];
113 c = times[j], d = times[j]+cost[j/2];
114 if(!(b<=c || d<=a)){
115 addedge(i,j^1);
116 addedge(j,i^1);
117 }
118 }
119 }
120 if(solve(2*n)){
121 puts("YES");
122 for(int i=0;i<2*n;i+=2){
123 int t1,t2;
124 if(dfn[belong[i]]<dfn[belong[i^1]])
125 t1 = times[i], t2 = t1+cost[i/2];
126 else t1 = times[i^1], t2 = t1+cost[i/2];
127 printf("%02d:%02d %02d:%02d
",t1/60,t1%60,t2/60,t2%60);
128 }
129 }else puts("NO");
130 }
131 return 0;
132 }
