题解：P9869 [NOIP2023] 三值逻辑
ylch
·
·
题解
发现每个 x_i 只有五种可能的值：T、F、U、x_j、\lnot x_j。
如果我们设 x_{n+1}=T,x_{n+2}=U，那么 F 也可以用 \lnot x_{n+1} 表示。这样所有元素就都可以表示成 x_i=x_j 或 x_i=\lnot x_j 的形式。
在输入时发现只有最后一次赋值会对 x_i 起实际影响，但其中的一些赋值操作也不是没用，可能会有关系上的影响。考虑先用类似并查集路径压缩的方式来存储每个结点对应的值（赋值结点）。
这样会形成互相独立的若干连通块，只要分开考虑即可。
我们希望使 U 的个数最小，考虑什么时候会用到 U。发现 U 可以适用于除了操作 1 之外的所有情况，所以一定是在一个连通块中赋值出现了矛盾（例如转一圈后回来出现了 x_i=\lnot x_i 的情况），那么就只能用 U 来解决。这样一整个连通块中所有数都只能是 U。
因为并查集不好处理遍历，所以考虑根据并查集建图。具体地，对所有具有赋值关系的 i,j 连无向边，若 x_i=x_j 边权为 0，若 x_i=\lnot x_j 边权为 1。（发现 n 个点 n 条边实际上是一个基环树）。
在图上我们应该怎么判断这种矛盾呢？发现如果 x_i 进行了奇数次取反后又回到 x_i，那么就出现了矛盾。也就是存在边权和为奇数的环。考虑用类似二分图染色的方法判定。
别忘了统计 x_{n+2}（U）所在的连通块，因为它们就算不矛盾也注定是 U。（别忘了减去 U 自己，因为 U 在题目中只是充当一个“标识”的作用，无实义）
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n, m; cin >> n >> m;
int T = n + 1, U = n + 2;
vector<int> fa(n + 5), t(n + 5); // 记录每个结点的值（赋值的结点）和是否取反
iota(fa.begin(), fa.end(), 0); // 初始化fa[i]=i
for(int i = 1; i <= m; i ++){
char op; cin >> op;
if(op == 'T'){
int x; cin >> x; fa[x] = T, t[x] = 0;
}
else if(op == 'F'){
int x; cin >> x; fa[x] = T, t[x] = 1;
}
else if(op == 'U'){
int x; cin >> x; fa[x] = U, t[x] = 0;
}
else if(op == '+'){
int x, y; cin >> x >> y;
fa[x] = fa[y], t[x] = t[y];
}
else if(op == '-'){
int x, y; cin >> x >> y;
fa[x] = fa[y], t[x] = t[y] ^ 1;
}
}
// 建无向图+染色判定
vector<int> vis(n + 5), val(n + 5); // 标记数组、染色权值
vector<array<int, 2>> G[n + 5];
for(int i = 1; i <= n; i ++){
G[fa[i]].push_back({i, t[i]}); G[i].push_back({fa[i], t[i]});
}
function<int(int,bool&)> dfs = [&](int u, bool &flag){ // 染色判定+计算连通块大小
vis[u] = 1;
int siz = 1;
for(auto [v, w] : G[u]){
if(vis[v] && val[v] != (val[u] ^ w)){
flag = false;
}
else if(!vis[v]){
val[v] = val[u] ^ w; siz += dfs(v, flag);
}
}
return siz;
};
int ans = 0;
for(int i = 1; i <= n; i ++){
if(!vis[i]){
bool flag = true; val[i] = 1; int siz = dfs(i, flag);
if(!flag) ans += siz; // 如果矛盾统计答案
}
}
// 处理U所在的连通块大小
fill(vis.begin(), vis.end(), 0); // 重置vis数组
function<int(int)> dfs2 = [&](int u){ // 搜索U所在连通块大小
vis[u] = 1;
int siz = 1;
for(auto [v, w] : G[u]){
if(!vis[v]) siz += dfs2(v);
}
return siz;
};
ans += dfs2(U) - 1; // 别忘了减去U自己
cout << ans << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
int c, T; cin >> c >> T;
while(T --) solve();
return 0;
}
```