学习博客
位运算转换为2-sat的方法：
x表示x这个点是0，x’表示x这个点是1
如果a and b<mark>0 连接a’->b b’->a
如果a and b</mark>1 连接a->a’ b->b’
如果a or b<mark>0 连接a’->a b’->b
如果a or b</mark>1 连接a->b’ b->a’
如果a xor b<mark>0 连接a->b b->a a’->b’ b’->a’
如果a xor b</mark>1 连接a->b’ b->a’ a’->b b’->a
文章目录
- 模板：
- [POJ 2723](http://poj.org/problem?id=2723)
- [zoj3656](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656)
- [hdu4115](http://acm.hdu.edu.cn/showproblem.php?pid=4115)
- [bzoj3495（前后缀优化建图）](https://www.lydsy.com/JudgeOnline/problem.php?id=3495)
- [bzoj4945](https://www.lydsy.com/JudgeOnline/problem.php?id=4945)
- [bzoj1997（平面图判定）](https://www.lydsy.com/JudgeOnline/problem.php?id=1997)
模板：
#include<bits/stdc++.h>
using namespace std;
const int N=16002,M=40002;
struct node{
int to,ne;
}e[M],e2[M];
int n,m,x,y,ans[N],low[N],dfn[N],bel[N],scc,tot,top,tim,in[N],inst[N],h2[N],opp[N],
col[N],h[N],st[N],tot2,q[N],i;
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void add2(int x,int y){
e2[++tot2]=(node){y,h2[x]};
h2[x]=tot2;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
for (int i=0;i<n;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n;i+=2){
if (bel[i]==bel[i|1]) return 0;
opp[bel[i]]=bel[i|1];
opp[bel[i|1]]=bel[i];
}
for (int i=0;i<n;i++)
for (int j=h[i],v;j;j=e[j].ne)
if (bel[i]!=bel[v=e[j].to]) add2(bel[v],bel[i]),in[bel[i]]++;
int l=0,r=0;
for (int i=1;i<=scc;i++)
if (!in[i]) q[r++]=i;
while (l<r){
int u=q[l++];
if (!col[u]) col[u]=1,col[opp[u]]=-1;
for (int i=h2[u],v;i;i=e2[i].ne){
in[v=e2[i].to]--;
if (!in[v]) q[r++]=v;
}
}
for (int i=0;i<n;i+=2)
if (col[bel[i]]==1) ans[i]=1;
return 1;
}
int main(){
scanf("%d%d",&n,&m);
n<<=1;
for (i=0;i<m;i++){
scanf("%d%d",&x,&y);
x--;y--;
add(x,y^1);
add(y,x^1);
}
if (!solve()) puts("NIE");
else for (i=0;i<n;i+=2) printf("%d\n",ans[i]?i|1:i+2);
}
POJ 2723
/*https://blog.csdn.net/jc514984625/article/details/71075089 m个门，每个门上有两把锁，打开一个就可以通过。 有2n个钥匙，每两个绑在一起，只能选用一个 ，选了一个，另一个就被废弃 问最多可以通过几扇门*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=1<<11,M=1<<12;
struct node{
int to,ne;
}e[M];
int n,m,x,y,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],key[N],i;
void init(){
M(dfn);M(inst);
top=scc=tim=0;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
for (int i=0;i<n;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n;i+=2)
if (bel[i]==bel[i|1]) return 0;
return 1;
}
int main(){
while (~scanf("%d%d",&n,&m) && n){
M(h);tot=0;
for (i=0;i<n;i++) scanf("%d%d",&x,&y),key[x]=i<<1,key[y]=i<<1|1;
n<<=1;
for (i=0;i<m;i++){
scanf("%d%d",&x,&y);
add(key[x]^1,key[y]);
if (x!=y) add(key[y]^1,key[x]);
init();
if (!solve()){
printf("%d\n",i);
break;
}
if (i==m-1) printf("%d\n",m);
}
for (i++;i<m;i++) scanf("%d%d",&x,&y);
}
}
zoj3656
#include<bits/stdc++.h>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=1002,M=500002;
struct node{
int to,ne;
}e[M];
int n,m,x,y,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],i,fl,ans,j,b[502][502],k;
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
for (int i=0;i<n<<1;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n<<1;i+=2)
if (bel[i]==bel[i|1]) return 0;
return 1;
}
void init(){
M(h);M(dfn);M(inst);
top=tot=scc=tim=0;
}
int main(){
while (~scanf("%d",&n)){
ans=1;
for (i=0;i<n;i++)
for (j=0;j<n;j++) scanf("%d",&b[i][j]);
for (i=0;i<n;i++){
if (b[i][i]) ans=0;
for (j=0;j<n;j++)
if (b[i][j]!=b[j][i]) ans=0;
}
if (!ans){
puts("NO");
continue;
}
for (k=0;k<31;k++){
init();
for (i=0;i<n;i++)
for (j=i+1;j<n;j++){
fl=b[i][j]&(1<<k);
x=i<<1;y=j<<1;
if ((i&1) && (j&1)){//or
if (fl) add(x,y^1),add(y,x^1);
else add(x^1,x),add(y^1,y);
}else if (!(i&1) && !(j&1)){//and
if (fl) add(x,x^1),add(y,y^1);
else add(x^1,y),add(y^1,x);
}else{//xor
if (fl) add(x,y^1),add(y,x^1),add(x^1,y),add(y^1,x);
else add(x,y),add(y,x),add(x^1,y^1),add(y^1,x^1);
}
}
if (!solve()){
ans=0;
puts("NO");
break;
}
}
if (ans) puts("YES");
}
}
hdu4115
/*https://www.cnblogs.com/kuangbin/archive/2012/10/07/2713999.html 有两个人玩一个石头剪刀布的游戏，两个人连续玩N轮，给出其中 一个人的N轮出的情况和该人对另外一个人的一些限制条件，有两种限制： 每种限制表示为：(a,b,c) ，如果c==0 则表示该人对另外一个人的限制为第a 局和第b局出的应该一样，如果c==1表示不一样，问另外一个人是否有赢的 可能。*/
#include<bits/stdc++.h>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=20002,M=40002;
struct node{
int to,ne;
}e[M];
int n,m,x,y,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],i,T,fl,a[N],b[N],z,ca;
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
M(dfn);M(inst);
top=scc=tim=0;
for (int i=0;i<n;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n;i+=2)
if (bel[i]==bel[i|1]) return 0;
return 1;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);fl=0;
tot=0;M(h);
for (i=0;i<n;i++){
scanf("%d",&a[i]);a[i]--;
b[i]=(a[i]+2)%3;
}
for (i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&z);x--;y--;
if (x==y && z==1) fl=1;
if (fl) continue;
if ((a[x]!=a[y])^z) add(x<<1,y<<1|1),add(y<<1,x<<1|1);
if ((a[x]!=b[y])^z) add(x<<1,y<<1),add(y<<1|1,x<<1|1);
if ((b[x]!=a[y])^z) add(x<<1|1,y<<1|1),add(y<<1,x<<1);
if ((b[x]!=b[y])^z) add(x<<1|1,y<<1),add(y<<1|1,x<<1);
}
n<<=1;
printf("Case #%d: ",++ca);
if (fl || !solve()) puts("no");
else puts("yes");
}
}
bzoj3495（前后缀优化建图）
//https://blog.csdn.net/zzkksunboy/article/details/76285426
#include<bits/stdc++.h>
using namespace std;
const int N=4e6;
struct node{
int to,ne;
}e[N<<1];
int n,m,x,y,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],i,k,j,las;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
for (int i=0;i<n;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n;i+=2)
if (bel[i]==bel[i|1]) return 0;
return 1;
}
int main(){
n=read();m=read();k=read();
for (i=0;i<m;i++){
x=read()-1;y=read()-1;
add(x<<1,y<<1^1);add(y<<1,x<<1^1);
}
for (i=0;i<n;i++) add(i<<1^1,i+n<<1^1),add(i+n<<1,i<<1);
for (i=0;i<k;i++){
m=read();
for (j=0;j<m;j++,las=x){
x=read();x--;
if (j) add(las+n<<1^1,x+n<<1^1),add(x+n<<1,las+n<<1),
add(x<<1^1,las+n<<1),add(las+n<<1^1,x<<1);
}
}
n<<=2;
puts(solve()?"TAK":"NIE");
}
bzoj4945
//https://www.cnblogs.com/HocRiser/p/8981446.html
#include<bits/stdc++.h>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=100002;
struct node{
int to,ne;
}e[N<<1];
struct kk{
int u,v,uw,vw;
}q[N];
int n,m,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],i,w,cnt,p[9],a[N];
char ch1,ch2,s[N];
int F(int x,int k){//ABC三个车道中x不能开，判断k在剩下两个车道中是靠左的一个还是靠右的一个
if (k==0 || k==1 && a[x]==0) return x<<1;
return x<<1|1;
}
char get(int x,int k){
if (k==0) return a[x]==0?'B':'A';//靠左
return a[x]==2?'B':'C';//靠右
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
void solve(){
M(dfn);M(inst);M(h);
tot=top=tim=scc=0;
for (int i=0;i<m;i++){
if (a[q[i].u]==q[i].uw) continue;
int u=F(q[i].u,q[i].uw),v=F(q[i].v,q[i].vw);
if (a[q[i].v]!=q[i].vw) add(u,v),add(v^1,u^1);
else add(u,u^1);
}
for (int i=0;i<n<<1;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n<<1;i+=2)
if (bel[i]==bel[i|1]) return;
for (int i=0;i<n;i++) putchar(get(i,bel[i<<1]>=bel[i<<1|1]));
exit(0);
}
void dfs(int x){
if (x>w){
solve();
return;
}
a[p[x]]=0;dfs(x+1);
a[p[x]]=1;dfs(x+1);
}
int main(){
scanf("%d%d%s%d",&n,&w,s,&m);
for (i=0;i<n;i++){
a[i]=s[i]-'a';
if (s[i]=='x') p[++cnt]=i;
}
for (i=0;i<m;i++){
scanf("%d %c%d %c",&q[i].u,&ch1,&q[i].v,&ch2);
q[i].u--;q[i].v--;
q[i].uw=ch1-'A';
q[i].vw=ch2-'A';
}
dfs(1);
puts("-1");
}
bzoj1997（平面图判定）
//https://blog.csdn.net/KikiDMW/article/details/68062538
#include<bits/stdc++.h>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=1202,M=720002;
struct node{
int to,ne;
}e[M];
int n,m,x,low[N],dfn[N],bel[N],scc,tot,top,tim,inst[N],h[N],st[N],i,T,pos[202],u[10002],v[10002],tmp,j;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
void init(){
M(dfn);M(inst);M(h);
top=tot=scc=tim=0;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
bool solve(){
for (int i=0;i<n;i++)
if (!dfn[i]) tarjan(i);
for (int i=0;i<n;i+=2)
if (bel[i]==bel[i|1]) return 0;
return 1;
}
int main(){
T=read();
while (T--){
n=read();m=read();
for (i=0;i<m;i++) u[i]=read()-1,v[i]=read()-1;
for (i=0;i<n;i++) x=read()-1,pos[x]=i;
if (m>n*3-6){
puts("NO");
continue;
}
init();
tmp=0;
for (i=0;i<m;i++){
u[i]=pos[u[i]];v[i]=pos[v[i]];
if (u[i]>v[i]) swap(u[i],v[i]);
if (u[i]+1==v[i] || u[i]==0 && v[i]==n-1) continue;
u[tmp]=u[i];v[tmp++]=v[i];
}
m=tmp;
for (i=0;i<m;i++)
for (j=i+1;j<m;j++)
if (u[i]<u[j] && u[j]<v[i] && v[i]<v[j] || u[j]<u[i] && u[i]<v[j] && v[j]<v[i]){
add(i<<1,j<<1^1);add(i<<1^1,j<<1);
add(j<<1,i<<1^1);add(j<<1^1,i<<1);
}
n=m<<1;
puts(solve()?"YES":"NO");
}
}
京公网安备 11010502036488号