【2019.8.14 慈溪模拟赛 T2】黑心老板（gamble）（2-SAT）

待我称王封你为后i 2021-10-29 11:16 144阅读 0赞

### \\(2-SAT\\) ###

考虑每个点只能选择\\(R\\)或\\(B\\)，可以看作选\\(0\\)或\\(1\\)。

然后对于给出的关系式，若其中一个位置满足关系式，另两个位置就必须不满足关系式，这样就可以对于每个关系式建出\\(6\\)条边。

然后就是裸的\\(Tarjan\\)求\\(2-SAT\\)一组解的板子了。

### 代码 ###

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 5000 #define K 10000 #define Gmin(x,y) (x>(y)&&(x=(y))) using namespace std; int n,k,a[K+5][5],p[K+5][5]; class TwoSatSolver//2-SAT { private: #define SZ 2*N #define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y) int ee,lnk[SZ+5],d,T,cnt,dfn[SZ+5],low[SZ+5],col[SZ+5],IS[SZ+5],S[SZ+5]; char ans[N+5];struct edge {int to,nxt;}e[6*K+5]; I void Tarjan(CI x,CI lst=0)//Tarjan缩点 { RI i;for(dfn[x]=low[x]=++d,IS[S[++T]=x]=1,i=lnk[x];i;i=e[i].nxt) dfn[e[i].to]?(IS[e[i].to]&&Gmin(low[x],dfn[e[i].to])) :(Tarjan(e[i].to,x),Gmin(low[x],low[e[i].to])); if(dfn[x]^low[x]) return;col[x]=++cnt,IS[x]=0; W(S[T]^x) col[S[T]]=cnt,IS[S[T--]]=0;--T; } public: I void Solve() { RI i;for(i=1;i<=k;++i)//根据给出的关系式建边 add(2*a[i][1]-p[i][1],2*a[i][2]-(p[i][2]^1)), add(2*a[i][1]-p[i][1],2*a[i][3]-(p[i][3]^1)), add(2*a[i][2]-p[i][2],2*a[i][1]-(p[i][1]^1)), add(2*a[i][2]-p[i][2],2*a[i][3]-(p[i][3]^1)), add(2*a[i][3]-p[i][3],2*a[i][1]-(p[i][1]^1)), add(2*a[i][3]-p[i][3],2*a[i][2]-(p[i][2]^1)); for(i=1;i<=2*n;++i) !dfn[i]&&(Tarjan(i),0);//Tarjan缩点 for(i=1;i<=n;++i) { if(col[2*i-1]==col[2*i]) return (void)puts("-1");//若两种情况在同一强连通分量中，无解 ans[i]=col[2*i-1]>col[2*i]?'R':'B';//选择所处强连通分量编号较小的，即拓扑序较大的 }puts(ans+1);//输出答案 } }S; int main() { freopen("gamble.in","r",stdin),freopen("gamble.out","w",stdout); RI i;char c[5];for(scanf("%d%d",&n,&k),i=1;i<=k;++i) scanf("%d%s%d%s%d%s",&a[i][1],&c[1],&a[i][2],&c[2],&a[i][3],&c[3]),//读入 p[i][1]=c[1]=='B',p[i][2]=c[2]=='B',p[i][3]=c[3]=='B';//转化 return S.Solve(),0; }

转载于:https://www.cnblogs.com/chenxiaoran666/p/Contest20190814T2.html