2-sat

快来打我* 2022-01-05 04:59 142阅读 0赞

### P3209 \[HNOI2010\]平面图判定 ###

#### 题目： ####

若能将无向图 $G=(V, E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图，图中存在一个包含所有顶点的环，即存在哈密顿回路。

#### 思路： ####

1.2-sat

关于平面图有一个性质，边数一定小于等于 $3n-6$ 。所以我们对于边数大的直接得到答案。其余的我们 $O(n^\{2\})$ 判断两条连边是否矛盾，把每条边分离成两个点表示边连在外部还是内部。如果矛盾就连边。

2.并查集

在一样的性质下，与 $i+n$ 相连的点表示不能与 $i$ 在同一侧，所以对于每对矛盾的边 $fa\[getfa(x)\]=getfa(y+n),fa\[getfa(y)\]=getfa(x+n)$ 。

如果如果有一对矛盾的点属于同一个集合，则不合法。

#### 代码： ####

我写的是第二种啊，感觉代码比较短...

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=1e4+5,M=1e4+5;
    int n,m,v[N],l[N],tot,id[N],fa[N];
    struct node{
        int x,y;
    }t[M];
    il int read(){
       int x,f=1;char ch;
       _(!)ch=='-'?f=-1:f;x=ch^48;
       _()x=(x<<1)+(x<<3)+(ch^48);
       return f*x;
    }
    il int getfa(int x){
        if(fa[x]==x)return x;return fa[x]=getfa(fa[x]);
    }
    il bool cross(int u1,int v1,int u2,int v2){
        u1=id[u1];v1=id[v1];u2=id[u2];v2=id[v2];
        if(u1>v1)swap(u1,v1);if(u2>v2)swap(u2,v2);
        return ((u1<u2&&u2<v1&&v1<v2)||(u2<u1&&u1<v2&&v2<v1));
    }
    int main()
    {
        int T=read();while(T--){
            n=read();m=read();
            for(int i=1;i<=m;i++)t[i].x=read(),t[i].y=read();
            for(int i=1;i<=n;i++)id[v[i]=read()]=i;
            if(m>3*n-6){puts("NO");continue;}
            for(int i=2;i<=n;i++)l[v[i]]=v[i-1];l[v[1]]=v[n];
            tot=0;
            for(int i=1;i<=m;i++)
                if(l[t[i].x]!=t[i].y&&l[t[i].y]!=t[i].x)t[++tot]=t[i];
            m=tot;
            for(int i=1;i<=(m<<1);i++)fa[i]=i;bool pd=0;
            for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++){
                if(!cross(t[i].x,t[i].y,t[j].x,t[j].y))continue;
                int x=getfa(i),y=getfa(j);
                if(x==y){pd=1;break;}
                fa[x]=getfa(j+m);fa[y]=getfa(i+m);
            }
            if(pd)puts("NO");else puts("YES");
        }
        return 0;
    }

## ##

### dtoj\#3858. 游戏 ###

#### 题目： ####

小 L 计划进行 $ n $ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。小 L 的赛车有三辆，分别用大写字母A、B、C表示。

地图一共有四种，分别用小写字母x、a、b、c表示。

其中，赛车A不适合在地图a上使用，赛车B不适合在地图b上使用，赛车C不适合在地图c上使用，而地图x则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 $ d $ 张。

$ n $ 场游戏的地图可以用一个小写字母组成的字符串描述。例如： $ S=xaabxcbc $ 表示小L计划进行 $ 8 $ 场游戏，其中第 $ 1 $ 场和第 $ 5 $ 场的地图类型是x，适合所有赛车，第2场和第3场的地图是a，不适合赛车A，第4场和第7场的地图是b，不适合赛车B，第6场和第8场的地图是c，不适合赛车C。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i,h\_i,j,h\_j) $ 来描述，表示若在第 $ i $ 场使用型号为 $ h\_i $ 的车子，则第 $ j $ 场游戏要使用型号为 $ h\_j $ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 $ -1 $ 。

####  思路： ####

当 $d=0$ 时对于每场比赛有两种选择，于是想到 $2-sat$ 。

考虑对于限制

如果 $i$ 场比赛不能放 $h\_\{i\}$ ，那就忽略这个限制。

如果第 $j$ 场不能放 $h\_\{j\}$ ，那就意味着不能在 $i$ 场放 $h\_\{i\}$ 那就连接 $(放 $h\_\{i\}$,不放 $h\_\{i\}$ )。

其他情况就是连接 (放 $h\_\{i\}$ ,放 $h\_\{j\}$ )，（不放 $h\_\{j\}$ ,不放 $h\_\{i\}$ ）。

#### 代码： ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=1e5+5;
    char s[N];bool vis[N];
    int sta[N],top,tot,col[N],c;
    int n,d,m,pos[N],cnt,head[N],ne[N<<1],to[N<<1],dfn[N],low[N];
    struct node{
        int x,y;char hx,hy;
    }t[N];
    il int read(){
       int x,f=1;char ch;
       _(!)ch=='-'?f=-1:f;x=ch^48;
       _()x=(x<<1)+(x<<3)+(ch^48);
       return f*x;
    }
    il char getc(){
        char ch='0';
        while(ch!='A'&&ch!='B'&&ch!='C')ch=getchar();
        return ch;
    }
    il void ins(int x,int y){
        ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;
    }
    il int id(int x,char ch,int op){
        if(op==1){
            if(s[x]=='a'){
                if(ch=='B')return x;return x+n;
            }
            if(s[x]=='b'){
                if(ch=='A')return x;return x+n;
            }
            if(s[x]=='c'){
                if(ch=='A')return x;return x+n;
            }
        }
        else{
            if(s[x]=='a'){
                if(ch=='B')return x+n;return x;
            }
            if(s[x]=='b'){
                if(ch=='A')return x+n;return x;
            }
            if(s[x]=='c'){
                if(ch=='A')return x+n;return x;
            }
        }
    }
    il void prin(int p,int op){
    //    printf("!!%d %d \n",b)
        if(s[p]=='a'){
            if(op==0)printf("B");else printf("C");
        }
        if(s[p]=='b'){
            if(op==0)printf("A");else printf("C");
        }
        if(s[p]=='c'){
            if(op==0)printf("A");else printf("B");
        }
    }
    il void tarjan(int x){
        dfn[x]=low[x]=++tot;sta[++top]=x;vis[x]=1;
        for(int i=head[x];i;i=ne[i]){
            if(!dfn[to[i]])tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
            else if(vis[to[i]])low[x]=min(low[x],dfn[to[i]]);
        }
        if(dfn[x]==low[x]){
            vis[x]=0;col[x]=++c;
            while(sta[top]!=x)vis[sta[top]]=0,col[sta[top--]]=c;
            top--;
        }
    }
    il bool pd(){
        cnt=0;
        for(int i=1;i<=(n<<1);i++)head[i]=dfn[i]=0;cnt=c=tot=0;
        for(int i=1;i<=m;i++){
            if(t[i].hx+32==s[t[i].x])continue;
            if(t[i].hy+32==s[t[i].y]){
                ins(id(t[i].x,t[i].hx,1),id(t[i].x,t[i].hx,0));
                continue;
            }
            ins(id(t[i].x,t[i].hx,1),id(t[i].y,t[i].hy,1));
            ins(id(t[i].y,t[i].hy,0),id(t[i].x,t[i].hx,0));
        }
        for(int i=1;i<=(n<<1);i++)if(!dfn[i])tarjan(i);
        for(int i=1;i<=n;i++)if(col[i]==col[i+n])return 0;
        for(int i=1;i<=n;i++){
            if(col[i]<col[i+n])prin(i,0);
            else prin(i,1);
        }
        return 1;
    }
    il void dfs(int x){
        if(x>d){
            if(pd())exit(0);
            return;
        }
        s[pos[x]]='a';dfs(x+1);
        s[pos[x]]='b';dfs(x+1);
    }
    int main()
    {
        n=read();read();
        scanf(" %s",s+1);
        for(int i=1;i<=n;i++)if(s[i]=='x')pos[++d]=i;
        m=read();
        for(int i=1;i<=m;i++){
            t[i].x=read();t[i].hx=getc();
            t[i].y=read();t[i].hy=getc();
        }
        dfs(1);puts("-1");
        return 0;
    }

## ##

### bzoj3495 PA2010 Riddle ###

#### 题目： ####

有 $n$ 个城镇被分成了 $k$ 个郡，有 $m$ 条连接城镇的无向边。

要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。

#### 思路： ####

有一个前缀建图的思路，对于每一个城镇去一个前缀和，因为一个城镇只能有一个首都，所以前缀和取值为 $0/1$ 。

于是有以下几种关系(前为条件后为结果)：

1. $a\[i\]=1,s\[i\]=1$

2. $s\[i\]=0,a\[i\]=1$

3. $a\[i\]=1,s\[i-1\]=0$

4. $s\[i-1\]=1,a\[i\]=0$

5. $s\[i-1\]=1,s\[i\]=1$

6. $s\[i\]=0,s\[i-1\]=0$

#### 代码： ####

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=4e6+5;
    bool vis[N];
    int col[N],sta[N],top,c;
    int n,m,k,head[N],ne[N<<1],to[N<<1],cnt,dfn[N],low[N],tot;
    il int read(){
       int x,f=1;char ch;
       _(!)ch=='-'?f=-1:f;x=ch^48;
       _()x=(x<<1)+(x<<3)+(ch^48);
       return f*x;
    }
    il void ins(int x,int y){
        ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;
    }
    il void tarjan(int x){
        dfn[x]=low[x]=++tot;sta[++top]=x;vis[x]=1;
        for(int i=head[x];i;i=ne[i]){
            if(!dfn[to[i]])tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
            else if(vis[to[i]])low[x]=min(low[x],dfn[to[i]]);
        }
        if(dfn[x]==low[x]){
            vis[x]=0;col[x]=++c;
            while(sta[top]!=x)vis[sta[top]]=0,col[sta[top--]]=c;
            top--;
        }
    }
    il bool pd(){
        for(int i=1;i<=n;i++)if(col[i]==col[i+n])return 0;
        for(int i=n*2+1;i<=n*3;i++)if(col[i]==col[i+n])return 0;
        return 1;
    }
    int main()
    {
        n=read();m=read();k=read();
        for(int i=1;i<=m;i++){
            int x=read(),y=read();
            ins(x+n,y);ins(y+n,x);
        }
        for(int i=1;i<=n;i++)ins(i,i+n*2),ins(i+n*3,i+n);
        for(int i=1;i<=k;i++){
            int d=read(),las=read();
            for(int j=2;j<=d;j++){
                int now=read();
                ins(now,las+n*3);ins(las+n*2,now+n);
                ins(las+n*2,now+n*2);ins(now+n*3,las+n*3);las=now;
            }
        }
        for(int i=1;i<=(n<<2);i++)if(!dfn[i])tarjan(i);
        if(pd())puts("TAK");else puts("NIE");
        return 0;
    }

转载于:https://www.cnblogs.com/Jessie-/p/11040631.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211230/cbee36b11e10436c8b46529b1a8fdeb5.png