洛谷：P1955：程序自动分析

题目

P1955：程序自动分析

分析

这道题目还是典型的并查集题目，“等式”一类的约束相当于“朋友”，可以直接归并；“不等式”一类的约束相当于“敌人”。举个例子：

\( \left\{\begin{matrix} x_1 = x_2 \\x_2 = x_3 \\x_3 = x_4 \\x_4\neq x_1 \end{matrix}\right. \)

前三个等式都可以简单归并成为一个集合。此时\(x_4\)的祖先也归并到了\(x_1\)。在处理不等式的时候，\(x_4\)和\(x_1\)有一个共同祖先——这表明它俩存在等式约束，所以出现了矛盾。因此就可以马上中断运行，约束条件已经无法全部满足了。

答案

思考

在用Trae编写时，它用了一些高级的语法（比如tuple，以及直接用{...}构建tuple，但是洛谷的编译器还比较老，不能编译。所以改用了更通用的语法。

另外，这里要用map<int, int>来保存祖先关系，因为给出的变量序号可能很大但很稀疏。

我下载了测试点2的输入数据（因为一开始在这里出现RE——数组下标的问题），竟然有14K，72万行！

251019再次解题

在深入浅出程序设计竞赛（进阶篇）第2章中，我们再次碰到了这个题目——这次用到了离散化。但我们的解法不需要用到离散化，因为我们用了STL中的map而避免了声明一个庞大的数组。

新的代码看起来更有组织，也更容易阅读。

• 用struct Constraint表示两个变量间的相等/不相等关系。
• 用class UnionFind实现了并查集中三个重要的函数：
  • find(int x)递归地查找“父”节点
  • unite(int x, int y)进行并查的合并
  • areConnected(int x, int y)判定两个节点是否有关联（即它们的父节点相同）
• 在solveProblem(const vector<Constraint>& constraints)中：
  • 所有“相等”的关系都可以直接放入UnionFind uf中的私有变量unordered_map<int, int> parent，后者保留了所有的相等关系。
  • 如果出现“不相等”的关系，那么检查x和y是否有相同的父节点。如果有，就说明两个变量通过某个或若干个之前的相等关系，存在“相等”关系，与此处出现的“不等”关系矛盾。函数可以直接返回false。

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// Constraint structure for better code readability
struct Constraint
{
    int var1, var2;
    bool isEqual;  // true for xi = xj, false for xi ≠ xj

    Constraint(int i, int j, int e) : var1(i), var2(j), isEqual(e == 1) {}
};

class UnionFind
{
   private:
    unordered_map<int, int> parent;

   public:
    int find(int x)
    {
        if (parent.find(x) == parent.end())
        {
            parent[x] = x;
        }
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }

    void unite(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
        {
            parent[rootX] = rootY;
        }
    }

    bool areConnected(int x, int y)
    {
        return find(x) == find(y);
    }
};

bool solveProblem(const vector<Constraint>& constraints)
{
    UnionFind uf;

    // Phase 1: Process all equality constraints (xi = xj)
    for (const auto& constraint : constraints)
    {
        if (constraint.isEqual)
        {
            uf.unite(constraint.var1, constraint.var2);
        }
    }

    // Phase 2: Check all inequality constraints (xi ≠ xj)
    for (const auto& constraint : constraints)
    {
        if (!constraint.isEqual)
        {
            if (uf.areConnected(constraint.var1, constraint.var2))
            {
                return false;  // Contradiction found
            }
        }
    }

    return true;  // All constraints can be satisfied
}

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        vector<Constraint> constraints;
        constraints.reserve(n);

        // Read all constraints
        for (int k = 0; k < n; k++)
        {
            int i, j, e;
            cin >> i >> j >> e;
            constraints.emplace_back(i, j, e);
        }

        // Solve and output result
        bool satisfiable = solveProblem(constraints);
        cout << (satisfiable ? "YES" : "NO") << endl;
    }

    return 0;
}