题解 | #程序自动分析#

题目链接

程序自动分析

题目描述

给定 $n$ 个形如 $x_i = x_j$ 或 $x_i \neq x_j$ 的约束条件，你需要判断是否存在一种对变量的赋值方案，能够同时满足所有这些约束。

输入包含 $T$ 个独立的测试用例。每个测试用例首先给出约束的数量 $n$ ，然后是 $n$ 行约束，每行格式为 $i, j, e$ ，其中：

如果 $e=1$ ，约束为 $x_i = x_j$ 。
如果 $e=0$ ，约束为 $x_i \neq x_j$ 。

对于每个测试用例，输出 "YES"（如果可满足）或 "NO"（如果不可满足）。

解题思路

这是一个典型的约束满足问题，可以使用并查集（Disjoint Set Union, DSU）来高效解决。

核心思想

相等关系：约束 $x_i = x_j$ 具有传递性。如果 $x_i = x_j$ 且 $x_j = x_k$ ，那么必然有 $x_i = x_k$ 。这正是并查集所描述的集合关系。我们可以用并查集将所有必须相等的变量“合并”到同一个集合中。
不相等关系：约束 $x_i \neq x_j$ 是一种“排斥”关系。
矛盾：当两个变量 $x_i$ 和 $x_j$ 一方面被要求必须相等（因为它们在同一个集合中），另一方面又被要求必须不相等时，就产生了矛盾。

算法流程

我们可以分两步处理所有约束：

处理所有相等约束：
- 遍历所有 $e=1$ 的约束 $(i, j, 1)$ 。
- 对于每一个这样的约束，我们在并查集中执行 unite(i, j) 操作。
- 完成这一步后，并查集中的每个集合都代表了一组必须彼此相等的变量。
检查所有不相等约束：
- 遍历所有 $e=0$ 的约束 $(i, j, 0)$ 。
- 对于每一个这样的约束，我们检查变量 $x_i$ 和 $x_j$ 是否在同一个集合中，即判断 find(i) == find(j) 是否成立。
- 如果成立，说明根据相等约束， $x_i$ 和 $x_j$ 必须相等，这与当前 $x_i \neq x_j$ 的约束矛盾。因此，整个问题无解。
- 如果遍历完所有的不相等约束都没有发现矛盾，说明存在可行的赋值方案，问题有解。

离散化

题目中的变量下标 $i, j$ 可能很大，但变量的总数是有限的。直接使用这些下标作为数组索引可能会导致内存超限。因此，我们需要进行离散化：将出现过的所有不重复的变量下标，映射到一个从 $0$ 开始的连续整数区间上。

我们可以使用 map (C++/Java) 或 dict (Python) 来实现这个映射。在读取约束时，为每个新出现的变量下标分配一个唯一的、递增的ID。后续所有并查集操作都使用这些映射后的ID。

完整步骤

对于每个测试用例：

创建一个 map 用于离散化，以及两个列表，分别存储相等和不相等约束。
读取所有 $n$ 个约束，填充这两个列表，并在这个过程中完成离散化，记录下总共有多少个不同的变量。
初始化并查集，其大小为不同变量的总数。
遍历相等约束列表，执行 unite 操作。
遍历不相等约束列表，执行 find 操作检查矛盾。
根据是否发现矛盾，输出 "YES" 或 "NO"。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <map>

using namespace std;

struct Constraint {
    int i, j, e;
};

vector<int> parent;

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        parent[b] = a;
    }
}

void solve() {
    int n;
    cin >> n;

    vector<Constraint> constraints(n);
    map<int, int> discrete_map;
    int id_counter = 0;

    for (int k = 0; k < n; ++k) {
        cin >> constraints[k].i >> constraints[k].j >> constraints[k].e;
        if (discrete_map.find(constraints[k].i) == discrete_map.end()) {
            discrete_map[constraints[k].i] = id_counter++;
        }
        if (discrete_map.find(constraints[k].j) == discrete_map.end()) {
            discrete_map[constraints[k].j] = id_counter++;
        }
    }

    parent.assign(id_counter, 0);
    iota(parent.begin(), parent.end(), 0);

    for (const auto& c : constraints) {
        if (c.e == 1) {
            unite_sets(discrete_map[c.i], discrete_map[c.j]);
        }
    }

    bool possible = true;
    for (const auto& c : constraints) {
        if (c.e == 0) {
            if (find_set(discrete_map[c.i]) == find_set(discrete_map[c.j])) {
                possible = false;
                break;
            }
        }
    }

    if (possible) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Constraint {
    int i, j, e;
    public Constraint(int i, int j, int e) {
        this.i = i;
        this.j = j;
        this.e = e;
    }
}

public class Main {
    private static int[] parent;

    private static int findSet(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = findSet(parent[v]);
    }

    private static void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();

        List<Constraint> constraints = new ArrayList<>();
        Map<Integer, Integer> discreteMap = new HashMap<>();
        int idCounter = 0;

        for (int k = 0; k < n; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            int e = sc.nextInt();
            constraints.add(new Constraint(i, j, e));

            if (!discreteMap.containsKey(i)) {
                discreteMap.put(i, idCounter++);
            }
            if (!discreteMap.containsKey(j)) {
                discreteMap.put(j, idCounter++);
            }
        }

        parent = new int[idCounter];
        for (int i = 0; i < idCounter; i++) {
            parent[i] = i;
        }

        for (Constraint c : constraints) {
            if (c.e == 1) {
                uniteSets(discreteMap.get(c.i), discreteMap.get(c.j));
            }
        }

        boolean possible = true;
        for (Constraint c : constraints) {
            if (c.e == 0) {
                if (findSet(discreteMap.get(c.i)) == findSet(discreteMap.get(c.j))) {
                    possible = false;
                    break;
                }
            }
        }

        if (possible) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

# 增加递归深度
sys.setrecursionlimit(200005)

parent = []

def find_set(v):
    if v == parent[v]:
        return v
    parent[v] = find_set(parent[v])
    return parent[v]

def unite_sets(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        parent[b] = a

def solve(tokens, token_idx):
    global parent
    n = int(tokens[token_idx])
    token_idx += 1
    
    constraints = []
    discrete_map = {}
    id_counter = 0

    end_idx = token_idx + n * 3
    
    # First pass for discretization and storing constraints
    temp_idx = token_idx
    for _ in range(n):
        i = int(tokens[temp_idx])
        j = int(tokens[temp_idx + 1])
        e = int(tokens[temp_idx + 2])
        temp_idx += 3
        
        constraints.append((i, j, e))
        if i not in discrete_map:
            discrete_map[i] = id_counter
            id_counter += 1
        if j not in discrete_map:
            discrete_map[j] = id_counter
            id_counter += 1

    parent = list(range(id_counter))

    for i, j, e in constraints:
        if e == 1:
            unite_sets(discrete_map[i], discrete_map[j])

    possible = True
    for i, j, e in constraints:
        if e == 0:
            if find_set(discrete_map[i]) == find_set(discrete_map[j]):
                possible = False
                break
    
    if possible:
        print("YES")
    else:
        print("NO")
        
    return end_idx

def main():
    tokens = sys.stdin.read().split()
    if not tokens:
        return

    t = int(tokens[0])
    token_idx = 1
    for _ in range(t):
        token_idx = solve(tokens, token_idx)

if __name__ == "__main__":
    main()

算法及复杂度

算法：带离散化的并查集 (Disjoint Set Union)
时间复杂度： $\mathcal{O}(N \cdot \log U)$ 或 $\mathcal{O}(N \cdot \alpha(U))$ ，取决于离散化和并查集操作。在一个测试用例中，设 $N$ 是约束数量，最多有 $2N$ 个不同的变量。
- 读取和离散化：使用 map 或 dict，每次查找和插入的平均时间是 $\mathcal{O}(\log U)$ 或 $\mathcal{O}(1)$ ，总时间约为 $\mathcal{O}(N \log U)$ 。
- 并查集操作：处理 $N$ 个约束，总时间约为 $\mathcal{O}(N \cdot \alpha(U))$ 。
- 因此，总时间复杂度由离散化主导，约为 $\mathcal{O}(N \log U)$ 。
空间复杂度： $\mathcal{O}(N)$ ，用于存储所有约束、离散化映射和并查集数组。