P15936 [TOPC 2021] A Hard Problem

滥用本题评测将被封号。

给定一个由 $n$ 个节点和 $m$ 条边组成的简单无向图。节点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。节点 $i$ 有一个非负整数值 $V_i$，边 $\{u, v\}$ 的权值 $W_{u,v}$ 定义为 $\| V_u \oplus V_v \|$，其中 $\oplus$ 是异或运算符（等同于 C 语言中的 `^`），$\| x \|$ 是非负整数 $x$ 的二进制表示中 1 的位数。 节点值 $V_1, V_2, \dots, V_n$ 必须满足 $q$ 个约束条件。每个约束条件可以表示为一个五元组 $(t, u, i, v, j)$： - 若 $t = 0$，则 $getBit(V_u, i) = getBit(V_v, j)$ - 若 $t = 1$，则 $getBit(V_u, i) \neq getBit(V_v, j)$ 其中函数 $getBit(x, i)$ 返回 $x$ 的第 $(i + 1)$ 个最低有效位。例如，$getBit(11, 0)$ 为 1，$getBit(11, 2)$ 为 0。在 C 语言中，若 $x$ 是 32 位无符号整数且 $i$ 是小于等于 31 的非负整数，则 $getBit(x, i)$ 可通过 `((x >> i) & 1U)` 计算。 不幸的是，当前某些节点的值缺失。你的任务是在不违反任何给定约束的条件下，为缺失的节点分配新的值，以最小化 $\sum_{\{u,v\} \in E} W_{u,v}$。请编写程序完成此任务。

输入由五个部分组成。第一部分包含一行，该行包含两个正整数 $n$ 和 $m$，分别表示节点数和边数。第二部分包含 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示给定图中的一条边 $\{u, v\}$。第三部分包含一行，该行包含 $n$ 个空格分隔的整数 $x_1, x_2, \dots, x_n$。对于任意 $k \in \{1, 2, \dots, n\}$，若节点值 $V_k$ 缺失，则 $x_k$ 为 -1；否则 $V_k$ 等于 $x_k$。第四部分包含一个整数 $q$，表示约束条件的个数。第五部分包含 $q$ 行，每行包含五个空格分隔的整数 $t, u, i, v, j$，表示 $(t, u, i, v, j)$ 是一个约束条件。

输出一个整数，表示在满足 $q$ 个约束条件下的最小值。若无法满足所有约束，则输出 -1。

- $1 \leq n \leq 1000$ - $1 \leq m \leq 5000$ - $-1 \leq V_i < 2^{16}$ - $0 \leq q \leq 8$ - $t \in \{0, 1\}$ - $0 \leq u, v < n$ - $0 \leq i, j < 16$ 翻译由 DeepSeek V3.2 完成