洛谷P9869 [NOIP2023] 三值逻辑题解

题目链接：P9869 [NOIP2023] 三值逻辑

题意：

小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中，一个变量的值可能为：真（\(\mathtt{True}\)，简写作 \(\mathtt{T}\)）、假（\(\mathtt{False}\)，简写作 \(\mathtt{F}\)）或未确定（\(\mathtt{Unknown}\)，简写作 \(\mathtt{U}\)）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 \(\lnot\)，其运算法则为： \[ \lnot \mathtt{T} = \mathtt{F}, \lnot \mathtt{F} = \mathtt{T}, \lnot\mathtt{U} = \mathtt{U} \]

现在小 L 有 \(n\) 个三值逻辑变量 \(x_1,\cdots, x_n\)。小 L 想进行一些有趣的尝试，于是他写下了 \(m\) 条语句。语句有以下三种类型，其中 \(\gets\) 表示赋值：

\(x_i \gets v\)，其中 \(v\) 为 \(\mathtt{T}, \mathtt{F}, \mathtt{U}\) 的一种；

\(x_i \gets x_j\)；

\(x_i \gets \lnot x_j\)。

一开始，小 L 会给这些变量赋初值，然后按顺序运行这 \(m\) 条语句。

小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 \(\mathtt{Unknown}\) 的变量尽可能少。

在本题中，你需要帮助小 L 找到 \(\mathtt{Unknown}\) 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

输入格式:

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 \(c\) 和 \(t\)，分别表示测试点编号和测试数据组数。对于样例，\(c\) 表示该样例与测试点 \(c\) 拥有相同的限制条件。

接下来，对于每组测试数据：

输入的第一行包含两个整数 \(n\) 和 \(m\)，分别表示变量个数和语句条数。

接下来 \(m\) 行，按运行顺序给出每条语句。

输入的第一个字符 \(v\) 描述这条语句的类型。保证 \(v\) 为 TFU+- 的其中一种。

若 \(v\) 为 TFU 的某一种时，接下来给出一个整数 \(i\)，表示该语句为 \(x_i \gets v\)；

若 \(v\) 为 +，接下来给出两个整数 \(i,j\)，表示该语句为 \(x_i \gets x_j\)；

若 \(v\) 为 -，接下来给出两个整数 \(i,j\)，表示该语句为 \(x_i \gets \lnot x_j\)。

输出格式：

对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中，\(\mathtt{Unknown}\) 变量个数的最小值。

数据范围：

\(1 \le t \le 6\)，\(1 \le n,m \le 10 ^ 5\)

对于每个操作，\(v\) 为 TFU+- 中的某个字符，\(1 \le i,j \le n\) 。

每个节点最终的值的来源一定是唯一的，因此不妨把 \(\mathtt{T,F,U}\) 当作节点

对于每条信息，我们只需要维护一个 fa 和一个 type ，分别表示值的来源和赋值类型（即赋值 / 取反）。

容易发现，给出的信息中，有一些信息会导致矛盾，也就是此时赋值 \(\mathtt{T}\) 或 \(\mathtt{F}\) 都不能满足题目要求

事实上，当一个环中出现的“取反边”数量为奇数时会产生矛盾，并且这与其中“赋值边”的数量无关

最后不要忘记统计 \(\mathtt{U}\) 的子节点构成的那些联通块。

时间复杂度 \(\mathcal{O}(n + m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,m,ok,T,U,fa[N],col[N]; char type[N],vis[N];
vector<pii> g1[N]; vector<int> g2[N];
int get_size(int u)
{
    vis[u] = 1; int sz = 1;
    for(auto [v, w] : g1[u])
    {
        if(vis[v]) {
            if(col[v] != (col[u] ^ w)) ok = 0;
        }else { col[v] = (col[u] ^ w); sz += get_size(v); }
    }
    return sz;
}
int count(int u)
{
    int sz = 1;
    for(auto v : g2[u]) sz += count(v);
    return sz;
}
void solve()
{
    cin >> n >> m; T = n + 1; U = n + 2;
    for(int i = 1; i <= n + 2; i++)
    {
        fa[i] = i, type[i] = 0; g1[i].clear(); g2[i].clear();
        col[i] = 0; vis[i] = 0;
    }
    for(int i = 1, x,y; i <= m; i++)
    {
        char op; cin >> op;
        if (op == 'T' || op == 'F' || op == 'U')
        {
            cin >> x;
            if(op == 'T') { fa[x] = T; type[x] = 0; }
            else if(op == 'F') { fa[x] = T; type[x] = 1; }
            else if(op == 'U') { fa[x] = U; type[x] = 0; }
        }else if(op == '+') {
            cin >> x >> y; fa[x] = fa[y], type[x] = type[y];
        }else if(op == '-') {
            cin >> x >> y; fa[x] = fa[y], type[x] = (type[y] ^ 1);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        g1[fa[i]].emplace_back(i, type[i]);
        g1[i].emplace_back(fa[i], type[i]);
    }
    int res = 0;
    for(int i = 1; i <= n; i++)
        if(!vis[i]) {
            ok = 1; col[i] = 1;
            int sz = get_size(i); if(!ok) res += sz;
        }
    for(int i = 1; i <= n; i++) g2[fa[i]].push_back(i);
    cout << (res += count(U) - 1) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _, Q; cin >> _ >> Q; while(Q--) solve();
    return 0;
}