【系列】 2-SAT

bzoj 1997 Planar

题目大意：

给一个存在曼哈顿回路的无向图，求该图是否为平面图

思路：

先把曼哈顿回路提出来，则剩下的边的两个端点若有$ABAB$的形式则这两条边必定一个在环外一个在环内

对于这些边$2-SAT$即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 2139062143
14 #define MAXN 20100
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define Fill(x,t) memset(x,t,sizeof(x))
19 #define pb(i,x) vec[i].push_back(x)
20 #define pls(a,b) (a+b)%MOD
21 #define mns(a,b) (a-b+MOD)%MOD
22 #define mul(a,b) (1LL*(a)*(b))%MOD
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
28     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,m,nxt[MAXN*100],fst[MAXN],to[MAXN*100],cnt,u[MAXN],v[MAXN],cir[MAXN];
32 int dfn[MAXN],low[MAXN],bl[MAXN],stp,st[MAXN],top,scc,hsh[MAXN];
33 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
34 void mem()
35 {
36     Fill(fst,0);Fill(dfn,0);Fill(cir,0);Fill(bl,0);
37     cnt=stp=top=scc=0;
38 }
39 int p(int x) {return u[x]%n+1==v[x]||(v[x]==n&&u[x]==1);}
40 void tarjan(int x)
41 {
42     st[++top]=x,dfn[x]=low[x]=++stp;
43     ren if(!dfn[to[i]]) {tarjan(to[i]);low[x]=min(low[x],low[to[i]]);}
44         else if(!bl[to[i]]) low[x]=min(low[x],dfn[to[i]]);
45     if(low[x]==dfn[x])
46         {scc++;int now=0;while(now!=x) now=st[top--],bl[now]=scc;}
47 }
48 int cheq(){rep(i,1,m) if(bl[i]==bl[i+m]&&cir[i]) return 0;return 1;}
49 int main()
50 {
51     int T=read();while(T--)
52     {
53         n=read(),m=read();mem();rep(i,1,m) u[i]=read(),v[i]=read();
54         rep(i,1,n) hsh[read()]=i;if(m>3*n-6){puts("NO");continue;}
55         rep(i,1,m) {u[i]=hsh[u[i]],v[i]=hsh[v[i]];if(u[i]>v[i]) swap(u[i],v[i]);}
56         rep(i,1,m) cir[i]=1^p(i);rep(i,1,m) rep(j,1,m)
57             if(cir[i]&&cir[j]&&i^j&&u[i]<u[j]&&u[j]<v[i]&&v[i]<v[j])
58                 add(i+m,j),add(i,j+m),add(j,i+m),add(j+m,i);
59         rep(i,1,m<<1) if(!dfn[i]&&cir[i]) tarjan(i);puts(cheq()?"YES":"NO");
60     }
61 }

View Code

bzoj 4945 游戏

题目大意：

有$n$个场地分为4种$x,a,b,c$，有三辆车$A$不能跑$a$，$B$不能跑$b$，$C$不能跑$c$，$x$所有都能跑

给出一些限制形如$i,x,j,y$表示若$i$场地选了$x$这种车，则$j$场地必须选$y$这种车

给出合法的安排车的方案或判断无解

思路：

每个不是$x$的场地可以选两种车，可以转化为$2-SAT$模型

因为$x$的场地很少，枚举每个场地作为$A$或$B$复杂度$2^D$，不需要枚举选哪个车

对每个限制，若$i$和$x$不合法，无视这个条件即可

若$j$和$y$不合法，相当于强行选$ eg x$

其余情况直接连这个限制与其逆否即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #define ll long long
12 #define db double
13 #define inf 2139062143
14 #define MAXN 200100
15 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)
16 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)
17 #define ren for(register int i=fst[x];i;i=nxt[i])
18 #define Fill(x,t) memset(x,t,sizeof(x))
19 #define pls(a,b) (a+b)%MOD
20 #define mns(a,b) (a-b+MOD)%MOD
21 #define mul(a,b) (1LL*(a)*(b))%MOD
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 int n,D,m,g[MAXN],st[MAXN],dfn[MAXN],low[MAXN],stp,scc,bl[MAXN],top;
31 int ux[MAXN],uy[MAXN],ox[MAXN],oy[MAXN],sp[10];
32 int nxt[MAXN<<1],to[MAXN<<1],fst[MAXN],cnt;
33 void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
34 struct Data{int a,id,b;};char s[MAXN],ta[2],tb[2];
35 void tarjan(int x)
36 {
37     st[++top]=x,dfn[x]=low[x]=++stp;
38     ren if(!dfn[to[i]]) {tarjan(to[i]);low[x]=min(low[x],low[to[i]]);}
39         else if(!bl[to[i]]) low[x]=min(low[x],dfn[to[i]]);
40     if(low[x]==dfn[x])
41         {scc++;int now=-1;while(now!=x) now=st[top--],bl[now]=scc;}
42 }
43 int calc(int id,int x) {return g[id]==3?(id<<1)+(x==2):(id<<1)+(x==3);}
44 int che()
45 {
46     Fill(dfn,0);Fill(bl,0);Fill(fst,0);top=scc=stp=cnt=0;int x,y;rep(i,1,m)
47     {
48         x=ux[i],y=uy[i];if(g[x]==ox[i]) continue;x=calc(x,ox[i]);
49         if(g[y]==oy[i]) {add(x,x^1);continue;}
50         y=calc(y,oy[i]);add(x,y);add(y^1,x^1);
51     }
52     rep(i,0,(n-1<<1)|1) if(!dfn[i]) tarjan(i);
53     rep(i,0,n-1) if(bl[i<<1]==bl[i<<1|1]) return 0;
54     rep(i,0,n-1) if(g[i]==1) printf("%c",(bl[i<<1]<bl[i<<1|1])?'B':'C');
55     else if(g[i]==2) printf("%c",(bl[i<<1]<bl[i<<1|1])?'A':'C');
56     else printf("%c",(bl[i<<1]<bl[i<<1|1])?'A':'B');return 1;
57 }
58 int main()
59 {
60     n=read(),D=read();int mxst=0;scanf("%s",s);rep(i,0,n-1)
61         {g[i]=s[i]-'a'+1;if(g[i]>3) g[i]=0,sp[mxst++]=i;}
62     m=read();rep(i,1,m) 
63     {
64         ux[i]=read()-1;scanf("%s",ta);uy[i]=read()-1;scanf("%s",tb);
65         ox[i]=ta[0]-'A'+1,oy[i]=tb[0]-'A'+1;
66     }
67     mxst=1<<D;if(!D) {if(!che()) printf("-1");return 0;}rep(t,0,mxst-1)
68         {rep(i,0,D-1) g[sp[i]]=((t>>i)&1)?2:1;if(che()) return 0;}printf("-1");
69 }

View Code