一道简单的 $\texttt{2-SAT}$ 题目。

题目链接：Luogu P3825/BZOJ 4945/NOI2017 D2T1。

题目

题目描述

小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 ABC 表示。地图一共有四种，分别用小写字母 xabc 表示。其中，赛车 A 不适合在地图 a 上使用，赛车 B 不适合在地图 b 上使用，赛车 C 不适合在地图 c 上使用，而地图 x 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $(i,h _ i,j,h _ j)$ 来描述，表示若在第 $i$ 场使用型号为 $h _ i$ 的车子，则第 $j$ 场游戏要使用型号为 $h _ j$ 的车子。

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

数据范围

时空限制

题解

思路

考虑 $d=0$ 的情况，发现是裸的 $\texttt{2-SAT}$。

又发现 $d$ 不太大，于是考虑每一个 x 处选择改为 a 或 b 来满足 $\texttt{2-SAT}$ 的条件，并且发现 c 的情况已经包含无需枚举，所以最多考虑 $2^d$ 次。

单次 $\texttt{2-SAT}$ 的时间复杂度为 $\Theta(n+m)$，所以程序的时间复杂度为 $O(2^d(n+m))$。

代码

程序的时间复杂度为 $O(2^d(n+m))$。

#include<bits/stdc++.h>
using namespace std;
#define reg register

const int MAXN=50000+5;
const int MAXM=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    ios::sync_with_stdio(false);
    Read();
    Work();
    return 0;
}

struct Rule{
    int i,hi,j,hj;
    inline void Read(void){
        static char a,b;
        cin>>i>>a>>j>>b;
        hi=a-'A',hj=b-'A';
        return;
    }
};

int n,d,m;
char str[MAXN];
Rule R[MAXM];

inline void Read(void){
    cin>>n>>d>>(str+1)>>m;
    for(reg int i=1;i<=m;++i)
        R[i].Read();
    return;
}

int cnt,head[MAXN<<1],to[MAXM<<1],Next[MAXM<<1];

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

bool vis[MAXN<<1];
int tim,dfn[MAXN<<1],low[MAXN<<1];
int top,S[MAXN<<1];
int Tarjan_cnt,color[MAXN<<1];

inline void Tarjan(reg int ID){
    dfn[ID]=low[ID]=++tim;
    vis[ID]=true;
    S[++top]=ID;
    for(reg int i=head[ID];i;i=Next[i])
        if(!dfn[to[i]]){
            Tarjan(to[i]);
            low[ID]=min(low[ID],low[to[i]]);
        }
    else if(vis[to[i]])
        low[ID]=min(low[ID],dfn[to[i]]);
    if(dfn[ID]==low[ID]){
        reg int To;
        ++Tarjan_cnt;
        do{
            To=S[top--];
            vis[To]=false;
            color[To]=Tarjan_cnt;
        }while(To!=ID);
    }
    return;
}

int p[MAXN];
int pos[MAXN][3];
int Ans[MAXN<<1];
int partner[MAXN<<1];

inline void Solve(void){
    cnt=0;
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    for(reg int i=1;i<=n;++i)
        partner[partner[i]=n+i]=i;
    for(reg int i=1;i<=m;++i)
        if(p[R[i].i]!=R[i].hi){
            reg int u=pos[R[i].i][R[i].hi],v=pos[R[i].j][R[i].hj];
            if(p[R[i].j]==R[i].hj)
                Add_Edge(u,partner[u]);
            else
                Add_Edge(u,v),Add_Edge(partner[v],partner[u]);
        }
    for(reg int i=1;i<=2*n;++i)
        if(!dfn[i])
            Tarjan(i);
    for(reg int i=1;i<=n;++i)
        if(color[i]!=color[i+n])
            partner[color[i+n]]=color[i],partner[color[i]]=color[i+n];
    else
        return;
    for(reg int i=1;i<=n;++i)
        putchar('A'+Ans[i+(color[i]<color[i+n]?0:n)]);
    exit(0);
    return;
}

vector<int> V;

inline void Work(void){
    for(reg int i=1;i<=n;++i)
        switch(p[i]=str[i]-'a'){
            case 0:{
                pos[i][1]=i,pos[i][2]=i+n;
                Ans[i]=1,Ans[i+n]=2;
                break;
            }
            case 1:{
                pos[i][0]=i,pos[i][2]=i+n;
                Ans[i]=0,Ans[i+n]=2;
                break;
            }
            case 2:{
                pos[i][0]=i,pos[i][1]=i+n;
                Ans[i]=0,Ans[i+n]=1;
                break;
            }
            default:break;
        }
    for(int i=1;i<=n;++i)
        if(p[i]>2)
            V.push_back(i);
    for(reg int i=0;i<(1<<d);++i){
        for(reg int j=0;j<d;++j)
            switch(p[V[j]]=((i>>j)&1)){
                case 0:{
                    pos[V[j]][1]=V[j],pos[V[j]][2]=V[j]+n;
                    Ans[V[j]]=1,Ans[V[j]+n]=2;
                    break;
                }
                case 1:{
                    pos[V[j]][0]=V[j],pos[V[j]][2]=V[j]+n;
                    Ans[V[j]]=0,Ans[V[j]+n]=2;
                    break;
                }
                case 2:{
                    pos[V[j]][0]=V[j],pos[V[j]][1]=V[j]+n;
                    Ans[V[j]]=0,Ans[V[j]+n]=1;
                    break;
                }
                default:break;
            }
        Solve();
    }
    puts("-1");
    return;
}