AT_arc161_e [ARC161E] Not Dyed by Majority (Cubic Graph) 题解
Jorisy
·
·
题解
这也太变态了。
首先证明一定有解。
设初始颜色序列 c\in S 映射到最终的颜色序列为 c'\in T。若 |S|>|T|，那么显然就会存在未被映射到的颜色序列。如果这个成立那么就有解。
令 $e(x)$ 表示与点 $x$ 直接相连的点的集合。设有一个点 $x$，$e(x)=\{u,v,w\}$，那么有 $e(u)=\{x,u_1,u_2\},e(v)=\{x,v_1,v_2\},e(w)=\{x,w_1,w_2\}$。
如果说 $c_{u_1}=c_{u_2},c_{v_1}=c_{v_2},c_{w_1}=c_{w_2}$，那么可以唯一确定 $c'_u=\lnot c_{u_1},c'_v=\lnot c_{v_1},c'_w=\lnot c_{w_1}$。这三个都被唯一确定了，那么 $c'_x$ 也是唯一确定的。
那么此时发现，$c_x$ 的值不影响 $c'$——换句话说，这个时候至少有 $2^{n-6}$ 种不同的 $c$ 对应着相同的 $c'$。
也就是说，如果我们随机一个 $c$，那么其无解的概率 $\ge\dfrac 1{64}$。事实上，根据官方题解的说法，这个概率大得多（$\approx0.48$）。不过我们估计的概率已经足以证明，我们可以 $O(1)$ 次随出一个合法方案。
那么现在的问题就是要如何 check 合法性。
考虑一下，我们的限制形如，设有节点 $x$ 以及 $e(x)=\{u,v,w\}$，「若 $c'_x\neq c_u$，则 $c'_x=c_v=c_w$」（轮换同理）。2-SAT 即可。
```cpp
#include<bits/stdc++.h>
#define N 50005
#define ll long long
#define mod
using namespace std;
mt19937_64 rnd(time(0));
vector<int>g0[N],g[N<<1];
int n,m,dfn[N<<1],low[N<<1],stk[N<<1],inst[N<<1],scc[N],cscc,ans[N];
void tarjan(int x)
{
dfn[x]=low[x]=++dfn[0];
stk[++stk[0]]=x;
inst[x]=1;
for(auto y:g[x])
{
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inst[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]^dfn[x]) return;
cscc++;
int y;
do
{
y=stk[stk[0]--];
inst[y]=0;
scc[y]=cscc;
}
while(x^y);
}
bool jd()
{
for(int i=1;i<=n*2;i++) g[i].clear();
for(int i=1;i<=n;i++)
{
for(auto x:g0[i])
{
for(auto y:g0[i])
{
if(x==y) continue;
g[x+(ans[i]^1)*n].push_back(y+ans[i]*n);
}
}
}
fill(scc,scc+n*2+1,0);
fill(dfn,dfn+n*2+1,0);
fill(low+1,low+n*2+1,0);
fill(inst+1,inst+n*2+1,0);
stk[0]=cscc=0;
for(int i=1;i<=n*2;i++)
{
if(dfn[i]) continue;
tarjan(i);
}
for(int i=1;i<=n;i++)
{
if(scc[i]^scc[i+n]) continue;
return 1;
}
return 0;
}
void sol()
{
cin>>n;
m=n*3/2;
for(int i=1;i<=n;i++) g0[i].clear();
while(m--)
{
int u,v;
cin>>u>>v;
g0[u].push_back(v);
g0[v].push_back(u);
}
while(1)
{
for(int i=1;i<=n;i++) ans[i]=rnd()&1;
if(!jd()) continue;
for(int i=1;i<=n;i++) cout<<"WB"[ans[i]];
cout<<'\n';
break;
}
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) sol();
return 0;
}
```